Posted on by Kalkicode
Code Binary Search Tree

Sum of alternate leaf nodes in bst in kotlin

Sum of alternate leaf nodes

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

// Kotlin program for
// Sum of alternate leaf nodes in bst
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	var alternate: Boolean;
	constructor()
	{
		this.root = null;
		this.alternate = false;
	}
	// Insert a new node element
	fun addNode(data: Int): Unit
	{
		// Create a new node
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			// When add first node in bst
			this.root = node;
		}
		else
		{
			var find: TreeNode ? = this.root;
			// Add new node to proper position
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						// 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 == null)
					{
						// When right child empty
						// So add new node here.
						find.right = node;
						return;
					}
					else
					{
						// Visit to right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	fun leafSum(node: TreeNode ? ): Int
	{
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// 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;
	}
	fun alternateLeafSum(): Int
	{
		// Reset alternate leaf node status
		this.alternate = false;
		return this.leafSum(this.root);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	/*
		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
	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