# spiral traversal of binary tree

June 11, 2013 5 Comments

This can be done using two stacks in iterative manner.

The below diagram depicts the spiral traversal of BST

**Steps to solve**

push level_1 nodes (i.e, only root node) into stack_1;

next by popping elements of level_1, push children of level_l in to stack_2 (i.e, level_2);

next by popping elements of level_2, push children of level_2 in to stack_2 (i.e, level_3);

… so on

Code:

/** * Algorithm to print binary tree in spiral manner * * @param node root node of the binary tree */ public void printTreeInSpiralForm(BinaryNode node) { Stack<BinaryNode> stack1 = new Stack<BinaryNode>(); Stack<BinaryNode> stack2 = new Stack<BinaryNode>(); stack1.push(node); while (!stack1.empty() || !stack2.empty()) { // while (!stack1.empty()) { node = stack1.pop(); if(node != null) { System.out.print(node.element+", "); if(node.left != null) stack2.push(node.left); if(node.right != null) stack2.push(node.right); } } while (!stack2.empty() && node != null) { node = stack2.pop(); if(node != null) { System.out.print(node.element+", "); if(node.left != null) stack1.push(node.right); if(node.right != null) stack1.push(node.left); } } } }

**Output:**

20, 25, 15, 12, 18, 22, 28, 32, 26, 24, 21, 19, 17, 14, 6

A single queue could also be used .

Initially Queue would be populated with root. A loop would iterate on the queue ,print the node ,pick a node add its right child and left child to the queue and so on till no elements are there in the queue.

@sreeram: doesn’t work.

it should work, send me the complete code

If node.left!=null. Why pushing node.right in stack1 ? And why stack2.empty== false instead of simply !stack2.empty()

Also we are never pushing null in stacks…so why checking for nulls ?