Help me understand Inorder Traversal without using recursion

Question

I am able to understand preorder traversal without using recursion, but I'm having a hard time with inorder traversal. I just don't seem to get it, perhaps, because I haven't understood the inner working of recursion.

This is what I've tried so far:

def traverseInorder(node):     lifo = Lifo()     lifo.push(node)     while True:         if node is None:             break         if node.left is not None:             lifo.push(node.left)             node = node.left             continue         prev = node         while True:             if node is None:                 break             print node.value             prev = node             node = lifo.pop()         node = prev         if node.right is not None:             lifo.push(node.right)             node = node.right         else:             break 

The inner while-loop just doesn't feel right. Also, some of the elements are getting printed twice; may be I can solve this by checking if that node has been printed before, but that requires another variable, which, again, doesn't feel right. Where am I going wrong?

I haven't tried postorder traversal, but I guess it's similar and I will face the same conceptual blockage there, too.

Thanks for your time!

P.S.: Definitions of Lifo and Node:

class Node:     def __init__(self, value, left=None, right=None):         self.value = value         self.left = left         self.right = right  class Lifo:     def __init__(self):         self.lifo = ()     def push(self, data):         self.lifo = (data, self.lifo)     def pop(self):         if len(self.lifo) == 0:             return None         ret, self.lifo = self.lifo         return ret 

Answer 1

Start with the recursive algorithm (pseudocode) :

traverse(node):   if node != None do:     traverse(node.left)     print node.value     traverse(node.right)   endif 

This is a clear case of tail recursion, so you can easily turn it into a while-loop.

traverse(node):   while node != None do:     traverse(node.left)     print node.value     node = node.right   endwhile 

You're left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we're in a "first run" situation (non-null node) or a "returning" situation (null node, non-empty stack) and runs the appropriate code:

traverse(node):   stack = []   while !empty(stack) || node != None do:     if node != None do: // this is a normal call, recurse       push(stack,node)       node = node.left     else // we are now returning: pop and print the current node       node = pop(stack)       print node.value       node = node.right     endif   endwhile 

The hard thing to grasp is the "return" part: you have to determine, in your loop, whether the code you're running is in the "entering the function" situation or in the "returning from a call" situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.

In this specific situation, we're using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow

traverse(node):   // entry:   if node == NULL do return   traverse(node.left)   // after-left-traversal:   print node.value   traverse(node.right)  traverse(node):    stack = [node,'entry']    while !empty(stack) do:      [node,state] = pop(stack)      switch state:         case 'entry':           if node == None do: break; // return          push(stack,[node,'after-left-traversal']) // store return address          push(stack,[node.left,'entry']) // recursive call          break;        case 'after-left-traversal':           print node.value;          // tail call : no return address          push(stack,[node.right,'entry']) // recursive call       end     endwhile  

Answer 2

Here is a simple in-order non-recursive c++ code ..

void inorder (node *n) {     stack s;      while(n){         s.push(n);         n=n->left;     }      while(!s.empty()){         node *t=s.pop();         cout<<t->data;         t=t->right;          while(t){             s.push(t);             t = t->left;         }     } }