Skip to main content

Reverse spiral traversal of a binary tree in scala

Scala program for Reverse spiral traversal of a binary tree. Here problem description and explanation.

/*
  Scala program for
  Reverse level order traversal in spiral form
*/
// 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);
	}
}
// Stack node
class StackNode(
	// Stack data
	var element: TreeNode,
		var next: StackNode);

// Define a custom stack
class MyStack(var top: StackNode,
	var size: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Add node at the top of stack
	def push(element: TreeNode): Unit = {
		this.top = new StackNode(element, this.top);
		this.size += 1;
	}
	def isEmpty(): Boolean = {
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	def pop(): Unit = {
		if (this.size > 0 && this.top != null)
		{
			// Change top element of stack
			this.top = this.top.next;
			this.size -= 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)
	}
	// Display tree element in reverse spiral level order traversal
	def reverseSpiral(): Unit = {
		if (this.root == null)
		{
			// Case
			// When empty
			println("Empty Tree");
			return;
		}
		// Empty stack
		var s1: MyStack = new MyStack();
		var s2: MyStack = new MyStack();
		var result: MyStack = new MyStack();
		// Some auxiliary variable
		var status: Int = 1;
		var node: TreeNode = this.root;
		// Add first node
		s1.push(node);
		while (node != null)
		{
			// Add node element into resultant stack
			result.push(node);
			if (status == 1)
			{
				// Add node from right to left
				// in s2 stack
				if (node.right != null)
				{
					// Add right child
					s2.push(node.right);
				}
				if (node.left != null)
				{
					// Add left child
					s2.push(node.left);
				}
			}
			else
			{
				// Add node from left to right
				// in s1 stack
				if (node.left != null)
				{
					// Add left child
					s1.push(node.left);
				}
				if (node.right != null)
				{
					// Add right child
					s1.push(node.right);
				}
			}
			if (status == 1)
			{
				// Case A
				// When execute s1 stack
				// Remove s1 element
				s1.pop();
				if (s1.isEmpty())
				{
					// When after remove s1 element
					// s1 stack empty.
					// Then change stack by s2
					status = 2;
					// Get first element of s2
					node = s2.peek();
				}
				else
				{
					// Otherwise get new top
					node = s1.peek();
				}
			}
			else
			{
				// Case B
				// When execute s2 stack
				// Remove s2 element
				s2.pop();
				if (s2.isEmpty())
				{
					// Here change stack
					status = 1;
					node = s1.peek();
				}
				else
				{
					node = s2.peek();
				}
			}
		}
		// Display final result
		while (result.isEmpty() == false)
		{
			// Get top element
			node = result.peek();
			// Display node value
			print("   " + node.data);
			// Remove top of stack
			result.pop();
		}
	}
}
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
		        
		*/
		// 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.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.right = new TreeNode(7);
		tree.root.right.left.right = new TreeNode(8);
		tree.root.right.right.right = new TreeNode(9);
		// Display reverse spiral level order element
		tree.reverseSpiral();
	}
}

Output

   9   8   7   4   5   6   3   2   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