Friday 5 August 2011

Iterative postorder traversal of Binary Tree Part-I

Iterative postorder traversal of Binary tree is tricky.  What makes it tricky is having to visit the same node multiple times and taking different actions on different visit. There are multiple ways of doing it. I have few of them coded in C# here.

Here is my node structure. Note I am using array to hold left and right pointers instead of Left and Right. Having children defined this way, reduces redundant code.

   1:  class Node
   2:  {
   3:      public int key;
   4:      public Node[] children = new Node[2];
   5:  }


I am going to use to Stack to keep track of nodes and associated visit count. The StackEntry is defined as follows
   1:  class StackEntry
   2:  {
   3:      public Node node;
   4:      public int visitcount;
   5:  }
 

Here is the code for PostOrder traversal of Binary Tree
   1:  public void PostOrder()
   2:  {
   3:      Stack<StackEntry> stack = new Stack<StackEntry>();
   4:      stack.Push(new StackEntry { node = root });
   5:      while (stack.Count > 0)
   6:      {
   7:          var top = stack.Peek();
   8:          if (top.visitcount < 2)
   9:          {
  10:              int direction = top.visitcount++;
  11:              if (top.node.children[direction] != null)
  12:              {
  13:                  stack.Push(new StackEntry { node = top.node.children[direction] });
  14:              }
  15:          }
  16:          else
  17:          {
  18:              stack.Pop();
  19:              Console.Write(" {0} ", top.node.key);
  20:          }
  21:      }
  22:  }

Above algorithm is doing following things:
  1. Initially root is wrapped inside StackEntry and pushed onto the stack.
  2. Inside while loop we look at stack's top element's visit count. 
  3. If visitcount == 0, then we push top element's left child provided it is non-null and increment the visitcount.
  4. If visitcount == 1, then we push top element's right child provided it is non-null and increment the visitcount.
  5. If visitcount ==2, then we pop the element and print its value.

No comments:

Post a Comment