Skip to main content

Sum of alternate leaf nodes in bst in golang

Sum of alternate leaf nodes

Go program for Sum of alternate leaf nodes in bst. Here mentioned other language solution.

package main
import "fmt"
// Go program for
// Sum of alternate leaf nodes in bst
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	// return new TreeNode
	return &TreeNode {
		data,
		nil,
		nil,
	}
}
type BinarySearchTree struct {
	root * TreeNode
	alternate bool
}
func getBinarySearchTree() * BinarySearchTree {
	// return new BinarySearchTree
	return &BinarySearchTree {
		nil,
		false,
	}
}
// Insert a new node element
func(this *BinarySearchTree) addNode(data int) {
	// Create a new node
	var node * TreeNode = getTreeNode(data)
	if this.root == nil {
		// When add first node in bst
		this.root = node
	} else {
		var find * TreeNode = this.root
		// Add new node to proper position
		for (find != nil) {
			if find.data >= data {
				if find.left == nil {
					// When left child empty
					// So add new node here
					find.left = node
					return
				} else {
					// Otherwise
					// Visit to left sub-tree
					find = find.left
				}
			} else {
				if find.right == nil {
					// When right child empty
					// So add new node here.
					find.right = node
					return
				} else {
					// Visit to right sub-tree
					find = find.right
				}
			}
		}
	}
}
func(this *BinarySearchTree) leafSum(node * TreeNode) int {
	if node != nil {
		if node.left == nil && node.right == nil {
			// Case A
			// When node is leaf node.
			// Change status.
			this.alternate = !this.alternate
			// Check node is alternate or not.
			if this.alternate {
				// When get alternate node.
				return node.data
			}
		} else {
			// Case B
			// When node is internal
			// Visit left and right subtree and
			// Find alternate node.
			return this.leafSum(node.left) + 
			this.leafSum(node.right)
		}
	}
	return 0
}
func(this *BinarySearchTree) alternateLeafSum() int {
	// Reset alternate leaf node status
	this.alternate = false
	return this.leafSum(this.root)
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	/*
		Binary search tree
	    -------------------
	       5
	      /  \  
	     /    \ 
	    /      \
	   3        19
	  / \     /   \
	 2   4   8     31
	       / \    / \
	      7   15 25  50  
	*/
	// Add tree node
	tree.addNode(5)
	tree.addNode(3)
	tree.addNode(19)
	tree.addNode(2)
	tree.addNode(4)
	tree.addNode(8)
	tree.addNode(31)
	tree.addNode(7)
	tree.addNode(25)
	tree.addNode(15)
	tree.addNode(50)
	// Test
	fmt.Println(tree.alternateLeafSum())
}

Output

34




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment