Post order traversal of binary tree without recursion

Question

Hello fellow coders,

Does anyone know the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion.

Any information would be greatly appreciated.

Answer 1

Here's a sample from wikipedia:

nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()

Answer 2

Here's a link which provides two other solutions without using any visited flags.

http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html

This is obviously a stack-based solution due to the lack of parent pointer in the tree. (We wouldn't need a stack if there's parent pointer).

We would push the root node to the stack first. While the stack is not empty, we keep pushing the left child of the node from top of stack. If the left child does not exist, we push its right child. If it's a leaf node, we process the node and pop it off the stack.

We also use a variable to keep track of a previously-traversed node. The purpose is to determine if the traversal is descending/ascending the tree, and we can also know if it ascend from the left/right.

If we ascend the tree from the left, we wouldn't want to push its left child again to the stack and should continue ascend down the tree if its right child exists. If we ascend the tree from the right, we should process it and pop it off the stack.

We would process the node and pop it off the stack in these 3 cases:

1. The node is a leaf node (no children)
2. We just traverse up the tree from the left and no right child exist.
3. We just traverse up the tree from the right.