Help me understand Inorder Traversal without using recursion

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 

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;        }    }}

def print_tree_in(root):    stack = []    current = root    while True:        while current is not None:            stack.append(current)            current = current.getLeft();        if not stack:            return        current = stack.pop()        print current.getValue()        while current.getRight is None and stack:            current = stack.pop()            print current.getValue()        current = current.getRight();