Inorder Tree Traversal without Recursion: GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

Problem Statement:
It is easy to traverse a binary tree in-order using recursion. Do it without using recursion.

Solution Idea:
It is possible to mimic the recursive behavior of an algorithm using stack. The algorithm is following (as described in the link):
– Create an empty stack S.
– Initialize current node as root
– Push the current node to S and set current = current->left until current is NULL
– If current is NULL and stack is not empty then
—- Pop the top item from stack.
—- Print the popped item, set current = current->right
—- Go to step 3.
– If current is NULL and stack is empty then we are done.

Solution Gist:

Advertisements

Tagged: , , , , , , , ,

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: