2
$\begingroup$

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()
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.