General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

Question

I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2, which I also copied below.

What confuses me most is that

• I find the non-recursive implementations using stacks are not easy to understand.

• It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations.

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Since a compiler can implement recursions using stacks, I believe it is possible to do that.

One reply I saw

Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:

foo(first);
foo(second);

has to be replaced by

stack.push(second);
stack.push(first);

In the idea of the reply, the non-recursive implementation of preorder is easier to understand than the non-recursive implemenations of the other two. The non-recursive implemenations of the other two don't seem to follow the idea at least closely, and can they be written to follow the idea closely?

Thanks.

---

Note the implementations from Wikipedia are

Pre-order

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

In-order

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

Post-order

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

Answer 1

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Yes, they can be reformulated in a unified way.

We take the <pre/in/post>_order recursive calls together with the visit procedure call, reverse them and push the corresponding nodes on the stack s, marking each node with its purpose: TRAVERSE or VISIT. I think the examples below explain the idea better.

Preorder traversal

So, iterativePreorder can be reformulated as

iterativePreorder(node)
  s ← empty stack
  s.push(<node, TRAVERSE>)

  while (not s.isEmpty())
    <node, mark> ← s.pop()
    if node = null
      continue
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
      s.push(<node, VISIT>)
    else
      visit(node)

It's easy to see the above pseudocode can be transformed into the iterativePreorder procedure provided in the question by

• eliminating two consecutive push/ pop operations on the same node;
• not pushing null-nodes on the stack.

In-order traversal

Skipping the boilerplate code, we get:

iterativeInorder(node)
...
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node, VISIT>)
      s.push(<node.left, TRAVERSE>)
...

Postorder traversal

iterativePostorder(node)
...
    if mark = TRAVERSE
      s.push(<node, VISIT>)
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
...

The iterativeInorder and iterativePostorder procedures cited in the question don't look like the above code because they make use of the traversal patterns arising in those cases. Like the fact that under in-order traversal we go straight to the leftmost leaf of the input tree, visit it, go one level up and do the same thing for the right subtree of the current node, etc.

Answer 2

"I find the non-recursive implementations using stacks are not easy to understand."

• One reason the complexity comes is due to "simulating" our own call-stack, which was done by compiler for the recursive method. The non-recursive variant may also include some optimization in addition to implementing what the recursive method does.

"It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations."

• There can be a unified way, which applies to all the 3 traversals. Though, as said above, we may apply optimizations to individual methods and they may start looking non-similar.

"Can they be reformulated and/or created from the recursive implementations in some unified way?"

• We can begin by knowing that we need to implement the recursive calls ourselves managing our own stack (this is done by compiler/program-stack automatically for recursive methods). The elements of our stack will need to track nodes and their state. The state will tell us what is the next task to do for that node, and any local-variables to remember. For example, which step of the recursive-method is to be executed next for that node. We can then have a loop which keeps on handling the topmost element of this stack based on its state, and also pushes/pops on this stack.

Take example of postorder traversal. We mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point").

void post(node *x)  
{  
  /* RP 0 */  
  if(x->lc) post(x->lc);  
  /* RP 1 */  
  if(x->rc) post(x->rc);  
  /* RP 2 */  
  process(x);  
}

Its iterative variant, which also includes an optimization as mentioned below:

void post_i(node *root)  
{  
  node *stack[1000];  
  int top;  
  node *popped;  
 
  stack[0] = root;  
  top = 0;  
  popped = NULL;  
 
#define POPPED_A_CHILD() \  
  (popped && (popped == curr->lc || popped == curr->rc))  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(!POPPED_A_CHILD())  
    {  
      /* type (x: 0) */  
      if(curr->rc || curr->lc)  
      {  
        if(curr->rc) stack[++top] = curr->rc;  
 
        if(curr->lc) stack[++top] = curr->lc;  
 
        popped = NULL;  
        continue;  
      }  
    }  
 
    /* type (x: 2) */  
    process(curr);  
    top--;  
    popped = curr;  
  }  
}

The code comments with (x: 0) and (x: 2) correspond to the "RP 0" and "RP 2" resume points in the recursive method.

Optimization: By pushing both the lc and rc pointers together, we have removed the need of keeping the post(x) invocation at resume-point 1 while the post(x->lc) completes its execution. That is, we could directly shift the node to "RP 2", bypassing "RP 1". So, there is no node kept on stack at "RP 1" stage.

Optimization: The POPPED_A_CHILD macro helps us deduce one of the two resume-points ("RP 0", or "RP 2"). Thus we have avoided the need to store, along with each node on stack, its state/resume-point.

You can read in detail about this general method applicable to all 3 traversals, and also individual optimizations possible, in this article written by me.