Binary Tree Postorder Traversal Non-recursive Version

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well the recursive solution is indeed trivial but quite elegant. However, sometimes we may hit a stack overflow exception and that’s why we need the iterative version. To convert a recursive solution into an iterative one, we have to implement our own stack.

So what should we put in our own stack? Think about the recursive version. For example, for each node that does not satisfy the condition of the base case, the function immediately calls on itself with the current node’s left child (if it exists), leaving its right child (if it exists) and its current value unprocessed. So the items going to the stack are nodes that are not fully processed: either its left or right child has not been visited yet.

So the stack is for tree nodes, but we also need to know whether the children of each node have been visited. The original node class does not support this. One simple solution is to wrap the TreeNode class in another class and I call it NodeInfo (it is a private class inside the PostorderTraversal class) and we create a stack of NodeInfo:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
private class NodeInfo{
    TreeNode node;
    boolean isLeftVisited;
    boolean isRightVisited;
    
    public NodeInfo(TreeNode node){
        this.node = node;
        isLeftVisited = false;
        isRightVisited = false;
        if(node.left == null) isLeftVisited = true;
        if(node.right == null) isRightVisited = true;
    }
}

OK, how does this work? Remember that for post order traversal, it has the following order:

  • Visit left subtree
  • Visit right subtree
  • Visit current node

So we can push our root wrapped in NodeInfo object to the stack. Then, as long as the stack is not empty:

  • we peek at the top node.
  • if the node has left child and it is not visited, set isLeftVisited to true and visitSubtree(left)
  • else if the node has right child and it is not visited, set isRightVisited to true and visitSubtree(right)
  • else if both children are visited, pop the top node and add its value to an ArrayList solution.

How do we visit the subtree?

while the node is not a leaf:

  • push itself to the stack
  • if it has unvisited  left child, set isLeftVisited to true and point itself to its left child
  • else if it has unvisited  right child, set isRightVisited to true and point itself to its right child

When the loop ends, the node should point to a leaf node so just add its value to the ArrayList solution.

I had trouble at first worrying about visiting only one side of a node in the loop, like we are missing them. But then I realized that all nodes with unvisited children are push to the stack along the way to the leaves so no worries.

Code on github:

Enhanced by Zemanta
Advertisements
Binary Tree Postorder Traversal Non-recursive Version

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s