9am

Tree Traversal Without Recursion

In Algorithms, Programming on August 15, 2010 at 7:22 pm

Tree traversal without recursion is slightly tricky using a stack especially if we want to do it without keeping track of visit state explicitly. Searching online, I could not find a good implementation. So I decided to write my own using stacks. If you are looking for a non-recursive, non-stack implementation, read up on Morris Traversal, which is based on Threaded Trees.

The following logic is largely derived from Donald Knuth’s implementation in ‘Art Of Computer Programming – 2.3.1’

In Order Traversal.

void PrintInOrder(Node root)
{

Stack stack = new Stack();
Node p = root;
while (p != null)
{

stack.Push(p);
// Update p
p = p.Left;

while (p == null && !stack.IsEmpty())
{

p = stack.Pop();
System.Console.WritelLine(p);
p = p.Right;

}

}

}

Pre Order Traversal

void PrintPreOrder(Node root)
{

Stack stack = new Stack();
Node p = root;
while (p != null)
{

System.Console.Writeline(p);
if (p.Right != null) stack.Push(p.Right);

// Update p
p = p.Left;

if (p == null && !stack.IsEmpty())
{

p = stack.Pop();

}

}

}

Post Order Traversal

void PrintPostOrder(Node root)
{

Stack result = new Stack();
Stack stack = new Stack();
Node p = root;
while (p != null)
{

result.Push(p);
if (p.Left != null) stack.Push(p.Left);
p = p.Right;
if(p == null && !stack.IsEmpty())
{

p = stack.Pop();

}

}

while(!result.IsEmpty())
{

System.Console.Writeline(result.Pop());

}

}

Advertisements

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

%d bloggers like this: