Sunday, January 1, 2012

Iterative or Non recursive Inorder traversal on tree

This process when implemented iteratively also requires a stack and a boolean to prevent the execution from traversing any portion of a tree twice. The general process of in-order traversal follows the following steps:
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

This iterative solution requires quite a few statements.  Recursively, the processing occurs between the two recursive calls.


// Recursive Inorder
void inorder(node *root)

{
  if(root)
  {
    inorder(root->left);
    printf("[%d] ", root->value);
    inorder(root->right);
  }
}


// Iterative Inorder using array as stack
void iterativeInorder (node *root)

{
  node *save[100];
  int top = 0;

  while(root != NULL)
  {
      while (root != NULL)
      {
           if (root->right != NULL)
           {
             save[top++] = root->right;
           }
           save[top++] = root;
           root = root->left;
      }

      root = save[--top];
      while(top != 0 && root->right == NULL)
      {
          printf("[%d] ", root->value);
          root = save[--top];
      }

      printf("[%d] ", root->value);
      root = (top != 0) ? save[--top] : (mynode *) NULL;
  }
}


Non recursive solution using stack
public  static <T> void inOrderNonRecursiveStack(BSTNode<T> root) {

 BSTNode<T> current = root;
 Stack<BSTNode<T>>  s = new Stack<BSTNode<T>>();  
 boolean done = false;
 while (!done)
 {
  
  if(current !=  null){  
     s.push(current);
     current = current.left;
  }
 
  else {
   if (!s.empty())
   {
    current = s.pop();
    System.out.print( current.data+" "); 
    current = current.right;
   }
   else
    done = true;
  }
 } 
} 

Another solution is to use Morris Traversal, which do not use stack, but inorder successor of the node to traverse.

0 comments:

Post a Comment