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