Skip to main content

Reverse level order traversal of binary tree in scala

Scala program for Reverse level order traversal of binary tree. Here more information.

/*
  Scala program for
  Reverse level order traversal of binary tree 
  By using stack and queue
*/
// 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);
	}
}
// Create node of (Queue,Stack)
class Node(var element: TreeNode,
	var next: Node)
{
	def this(node: TreeNode)
	{
		this(node, null);
	}
}
class MyQueue(var head: Node,
	var tail: Node,
		var count: Int)
{
	def this()
	{
		this(null, null, 0);
	}
	def size(): Int = {
		return this.count;
	}
	def isEmpty(): Boolean = {
		return this.count == 0;
	}
	// Add new node of queue
	def enqueue(value: TreeNode): Unit = {
		// Create a new node
		var x: Node = new Node(value);
		if (this.head == null)
		{
			// Add first element into queue
			this.head = x;
		}
		else
		{
			// Add node at the end using tail
			this.tail.next = x;
		}
		this.count += 1;
		this.tail = x;
	}
	// Delete a element into queue
	def dequeue(): Unit = {
		if (this.head == null)
		{
			// Empty Queue
			return;
		}
		// Visit next node
		this.head = head.next;
		this.count -= 1;
		if (this.head == null)
		{
			// When deleting a last node of linked list
			this.tail = null;
		}
	}
	// Get front node
	def peek(): TreeNode = {
		if (this.head == null)
		{
			return null;
		}
		return this.head.element;
	}
}
// Define a custom stack
class MyStack(var top: Node,
	var count: Int)
{
	def this()
	{
		this(null, 0)
	}
	def size(): Int = {
		return this.count;
	}
	// Add node at the top of stack
	def push(element: TreeNode): Unit = {
		// Create new node
		var x: Node = new Node(element);
		x.next = this.top;
		// Make new top
		this.top = x;
		this.count += 1;
	}
	def isEmpty(): Boolean = {
		if (this.size() > 0)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	def pop(): Unit = {
		if (this.size() > 0)
		{
			// Change top element of stack
			this.top = this.top.next;
			this.count -= 1;
		}
	}
	// Return top element of stack
	def peek(): TreeNode = {
		if (this.size() == 0)
		{
			return null;
		}
		return this.top.element;
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null)
	}
	def reverseLevelOrder(): Unit = {
		if (this.root != null)
		{
			var q: MyQueue = new MyQueue();
			var s: MyStack = new MyStack();
			// Add first node
			q.enqueue(this.root);
			var node: TreeNode = this.root;
			while (q.isEmpty() == false && node != null)
			{
				if (node.right != null)
				{
					// Add right child node
					q.enqueue(node.right);
				}
				if (node.left != null)
				{
					// Add left child node
					q.enqueue(node.left);
				}
				// Add the resultant node
				s.push(node);
				// Remove current node
				q.dequeue();
				// Get new head
				node = q.peek();
			}
			// Display result
			while (s.isEmpty() == false)
			{
				// Get top element
				node = s.peek();
				// Display level node
				print("   " + node.data);
				// Remove top
				s.pop();
			}
		}
		else
		{
			println("Empty Tree");
		}
	}
}
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
		        
		*/
		// Add node
		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.right.right = new TreeNode(10);
		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.left = new TreeNode(8);
		tree.root.right.left.right = new TreeNode(9);
		// Display the reverse level order elements
		tree.reverseLevelOrder();
	}
}

Output

   7   8   9   10   4   5   6   2   3   1




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