spiral traversal of binary tree

This can be done using two stacks in iterative manner.

The below diagram depicts the spiral traversal of BST
SpriralBST

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

Advertisements

5 Responses to spiral traversal of binary tree

  1. sreeram says:

    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.

  2. @sreeram: doesn’t work.

  3. it should work, send me the complete code

  4. ankit says:

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

  5. ankit says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey