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

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

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 _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()

  while (not s.isEmpty())
     ← s.pop()
    if node = null
      continue
    if mark = TRAVERSE
      s.push()
      s.push()
      s.push()
    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()
      s.push()
      s.push()
...

Postorder traversal

iterativePostorder(node)
...
    if mark = TRAVERSE
      s.push()
      s.push()
      s.push()
...

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.

StackExchange Computer Science Q#65348, answer score: 3