Posted on by Kalkicode
Code Binary Search Tree

Sum of leaf node in BST using recursion in scala

Sum of leaf nodes

Scala program for Sum of leaf node in BST using recursion. Here mentioned other language solution.

// Scala program for
// Sum of all leaf nodes of binary search tree
// Using recusion
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null)
	}
}
class BinarySearchTree(var root: TreeNode)
{
	def this()
	{
		this(null)
	}
	// insert a new node
	def addNode(data: Int): Unit = {
		// Create a new node
		var node: TreeNode = new TreeNode(data);
		if (this.root == null)
		{
			// When adds a 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 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 right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	// Sum of leaf nodes
	def leafNodeSum(node: TreeNode): Int = {
		if (node != null)
		{
			if (node.left == null && node.right == null)
			{
				// When node is leaf node
				return node.data;
			}
			// Visit to left and right subtree
			return leafNodeSum(node.left) + leafNodeSum(node.right);
		}
		return 0;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		// Add nodes in binary search tree
		/*
		            5
		          /   \ 
		         /     \
		        3       9
		       / \     /  \
		      2   4   8    10
		             / 
		            6

		*/
		tree.addNode(5);
		tree.addNode(3);
		tree.addNode(9);
		tree.addNode(2);
		tree.addNode(4);
		tree.addNode(8);
		tree.addNode(10);
		tree.addNode(6);
		// Test
		print(tree.leafNodeSum(tree.root));
	}
}

Output

22

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