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

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


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.