Skip to main content

Top view of binary tree using recursion in scala

Scala program for Top view of binary tree using recursion. Here problem description and explanation.

/* 
  Scala program for
  Top view of binary tree using dfs
*/
// Binary Tree Node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode,
	var level: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Print left side top nodes including root
	def printleftSide(node: TreeNode, depth: Int): Unit = {
		if (node != null)
		{
			if (this.level < depth)
			{
				// Print the resultant node
				print("  " + node.data);
				this.level = depth;
			}
			// Recursively
			// Visit left subtree
			printleftSide(node.left, depth + 1);
			// Visit right subtree
			printleftSide(node.right, depth - 1);
		}
	}
	// Print right side top nodes
	def printRightSide(node: TreeNode, depth: Int): Unit = {
		if (node != null)
		{
			if (this.level < depth)
			{
				// Print the resultant node
				print("  " + node.data);
				this.level = depth;
			}
			// Recursively
			// First visit right subtree
			printRightSide(node.right, depth + 1);
			// Then
			// Visit left subtree
			printRightSide(node.left, depth - 1);
		}
	}
	// This is handle the request of printing top view
	def topView(): Unit = {
		this.level = -1;
		printleftSide(this.root, 0);
		this.level = 0;
		printRightSide(this.root, 0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new tree
		var tree: BinaryTree = new BinaryTree();
		/*
		   Make A Binary Tree
		-----------------------
		         1
		       /   \
		      2     3
		     /     / \
		    4     5   6
		   /       \    
		  7         8    
		             \
		              9
		               \
		                10
		*/
		// Construct binary tree
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(6);
		tree.root.right.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.left = new TreeNode(7);
		tree.root.right.left.right = new TreeNode(8);
		tree.root.right.left.right.right = new TreeNode(9);
		tree.root.right.left.right.right.right = new TreeNode(10);
		// Display top view
		tree.topView();
	}
}

Output

  1  2  4  7  3  6  10




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