9am

Archive for August, 2010|Monthly archive page

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());

}

}