## Archive for the ‘Algorithms’ Category

## What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on**September 16, 2010**at

**9:49 pm**

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

}

}