Skip to main content

Reverse spiral traversal of a binary tree in java

Java program for Reverse spiral traversal of a binary tree. Here problem description and other solutions.

/*
  Java program for
  Reverse level order traversal in spiral form
*/
// Binary Tree Node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Stack node
class StackNode
{
	// Stack data
	public TreeNode element;
	public StackNode next;
	public StackNode(TreeNode element, StackNode top)
	{
		this.element = element;
		this.next = top;
	}
}
// Define a custom stack
class MyStack
{
	public StackNode top;
	public int size;
	public MyStack()
	{
		// Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	public void push(TreeNode element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	public boolean isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public void pop()
	{
		if (this.size > 0 && this.top != null)
		{
			// Change top element of stack
			this.top = this.top.next;
			this.size--;
		}
	}
	// Return top element of stack
	public TreeNode peek()
	{
		if (this.size == 0)
		{
			return null;
		}
		return this.top.element;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root
		this.root = null;
	}
	// Display tree element in reverse spiral level order traversal
	public void reverseSpiral()
	{
		if (this.root == null)
		{
			// Case
			// When empty
			System.out.println("Empty Tree");
			return;
		}
		// Empty stack
		MyStack s1 = new MyStack();
		MyStack s2 = new MyStack();
		MyStack result = new MyStack();
		// Some auxiliary variable
		int status = 1;
		TreeNode node = 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
			System.out.print("   " + node.data);
          	// Remove top of stack
			result.pop();
		}
	}
	public static void main(String[] args)
	{
		// Create new tree
		BinaryTree tree = 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