Binary Tree Postorder traversal

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?

Among all the three tree traversal methods, the postorder is the tricky one.
There are actually several ways of doing that even besides the recursive one. Here, I will try to introduce the most intuitive and easiest one.

In order to store the order, we need two stacks here instead of one.

Before start, let’s recall how we do the preorder first. In the preorder traversal, we use a stack storing the sequence. The way we push nodes is Right ==> Left. Why? Because we could get the order of Left ==> Right when popping out the node in this way. However, for post order, we need exactly opposite sequence. So, we need to push left child first to the stack and then right.

Given the example above:
1
\
2
/
3
The first stack should be like: 123

We could see this order is totally opposite to the one we need. Because this is the order of root==>right==>left. And what we need for the postorder traversal is: left ==> right ==> root. So that’s why we need another extra stack to reverse the order.

Here is the code:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<TreeNode> output = new Stack<TreeNode>();
        
        if (root == null) {
            return list;
        }
        stack.push(root);
        while(!stack.empty()) {
            TreeNode node = stack.pop();
            output.push(node);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        while (!output.empty()) {
            list.add(output.pop().val);
        }
        return list;
    }
}

Advertisements

One thought on “Binary Tree Postorder traversal

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s