Definition

• inorder(node.left)
• visit node
• inorder(node.right)

It is easy to write a recursive version.

Convert to an iterative version

There are a lot of articles about how to do this using a stack, but, I have no enough memory to understand why they are using stack like that. As a result, I am going to write a function call simulating verison.

What happens when call to a function and return from a function

Call

• save all local vars
• save current code address (continue executing after callee returned)
• put params somewhere
• jump to the function

Return

• retore all local vars
• jump to saved caller code address

Simulating address

switch is a good idea.

(function entrance)
  
  // return or new call start
  
  take params from somewhere
  take saved address from somewhere

  switch saved address
    Line 1:
      
      do something
     
    Line 100:
    
      do someting
      
      // making call
      save some var
      save next address 250
      
      put some param for new call
      jump to (function entrance)
      
    
    Line 250:
    
      do something

Back to the problem

• Use a stack to save state, a state contains a param TreeNode and a return address.
• Use a loop to execute all state (simulating recursive function call)
• whenever there need a new call to function
  • push current state to stack
  • create and push a new state with param to stack
  • jump to loop begin

while stack is not empty

   current = stack.pop()

   switch current.returnAddress
   
   PRE:
      stack.push current
      
      new state { returnAddress = IN, param = current.left }
      stack.push new state
   
   IN:
      visit current.param
      
      
   POST:
      
      stack.push current
      
      new state { returnAddress = DONOTHING, param = current.right }
      stack.push new state
      ...