Posted on by Kalkicode
Code Binary Tree

Find top three elements of binary tree in scala

Finding top 3 maximum node in binary tree

Scala program for Find top three elements of binary tree. Here mentioned other language solution.

/* 
  Scala program for
  Find top three elements in binary tree
*/
// Node of Binary Tree
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 first: TreeNode,
		var second: TreeNode,
			var third: TreeNode)
{
	def this()
	{
		this(null, null, null, null);
	}
	// Recursive function
	// Display preorder view of binary tree
	def preOrder(node: TreeNode): Unit = {
		if (node != null)
		{
			//Print node value
			print("  " + node.data);
			preOrder(node.left);
			preOrder(node.right);
		}
	}
	// Find top three largest nodes in binary tree
	def getTopThree(node: TreeNode): Unit = {
		if (node != null)
		{
			if (this.first == null)
			{
				// First node of tree
				this.first = node;
			}
			else if (this.first.data < node.data)
			{
				// When get new first largest node
				// Interchange the node values
				this.third = this.second;
				this.second = this.first;
				this.first = node;
			}
			else if (this.second == null)
			{
				if (this.first.data != node.data)
				{
					// Get second largest node
					this.second = node;
				}
			}
			else
			{
				if (this.second.data < node.data && 
                    this.first.data > node.data)
				{
					// When we get new second largest
					// Replace the third node with the second node
					this.third = second;
					// This is new second largest element
					this.second = node;
				}
				else if (this.third == null)
				{
					if (this.second.data > node.data && 
                        this.first.data > node.data)
					{
						// Get the third largest node
						this.third = node;
					}
				}
				else if (this.third.data < node.data && 
                         this.first.data > node.data && 
                         this.second.data > node.data)
				{
					this.third = node;
				}
			}
			// Recursively, execute left and right subtree
			getTopThree(node.left);
			getTopThree(node.right);
		}
	}
	// This are handle the request to finding
	// top three nodes in binary tree.
	def printTopThree(): Unit = {
		if (this.root == null)
		{
			return;
		}
		// Display tree elements
		print("\n Preorder : ");
		preOrder(this.root);
		// Set the initial all three nodes
		this.first = null;
		this.second = null;
		this.third = null;
		// Find three largest element
		getTopThree(this.root);
		// Display calculated result
		println("\n First : " + first.data);
		if (second != null && 
            second != first && 
            second.data < first.data)
		{
			println(" Second : " + second.data);
		}
		else
		{
			println(" Second : None ");
		}
		if (third != null && third != second && 
            third != first && third.data < second.data)
		{
			println(" Third : " + third.data);
		}
		else
		{
			println(" Third : None");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create two trees
		var x: BinaryTree = new BinaryTree();
		var y: BinaryTree = new BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		           10
		          /  \
		         /    \
		        6      8
		       / \    / \
		      12  3  7   5
		     /        \   \
		    9         -6  13
		*/
		// Add nodes
		x.root = new TreeNode(10);
		x.root.left = new TreeNode(6);
		x.root.left.left = new TreeNode(12);
		x.root.right = new TreeNode(8);
		x.root.right.right = new TreeNode(5);
		x.root.right.left = new TreeNode(7);
		x.root.right.left.right = new TreeNode(-6);
		x.root.left.right = new TreeNode(3);
		x.root.left.left.left = new TreeNode(9);
		x.root.right.right.right = new TreeNode(13);
		/*
		    Construct Tree
		    --------------
		         1
		        / \ 
		       /   \
		      1     2
		     /     / \
		    1     2   2
		*/
		// Add second tree node
		y.root = new TreeNode(1);
		y.root.left = new TreeNode(1);
		y.root.right = new TreeNode(2);
		y.root.right.right = new TreeNode(2);
		y.root.right.left = new TreeNode(2);
		y.root.left.left = new TreeNode(1);
		// Test One
		x.printTopThree();
		// Test Two
		y.printTopThree();
	}
}

Output

 Preorder :   10  6  12  9  3  8  7  -6  5  13
 First : 13
 Second : 12
 Third : 10

 Preorder :   1  1  1  2  2  2
 First : 2
 Second : 1
 Third : None

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