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:

Create an empty stack S.
Initialize current node as root
Push the current node to S and set current = current->left until current is NULL
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.
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.

See also