Post Order Tree Traversal in Java (Time Complexity: O(n))

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

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

Understanding the Problem

The core challenge of this problem is to traverse a binary tree in postorder, which means visiting the left subtree, then the right subtree, and finally the root node. This traversal is significant in various applications such as expression tree evaluations and syntax tree traversals in compilers.

Potential pitfalls include misunderstanding the traversal order and handling null nodes incorrectly.

Approach

To solve this problem, we can consider both recursive and iterative approaches:

Recursive Approach

The recursive approach is straightforward. We define a helper function that recursively visits the left subtree, right subtree, and then the root node.

Iterative Approach

The iterative approach is more complex but can be achieved using a stack. We use two stacks to simulate the postorder traversal. The first stack is used to traverse the tree, and the second stack is used to store the nodes in postorder.

Algorithm

Recursive Algorithm

Define a helper function that takes a node and a list to store the result.
If the node is null, return.
Recursively call the helper function on the left subtree.
Recursively call the helper function on the right subtree.
Add the node's value to the result list.

Iterative Algorithm

Initialize two stacks: stack1 and stack2.
Push the root node to stack1.
While stack1 is not empty:

Pop a node from stack1 and push it to stack2.
Push the left child of the popped node to stack1 (if it exists).
Push the right child of the popped node to stack1 (if it exists).

While stack2 is not empty, pop from stack2 and add the value to the result list.

Code Implementation

Recursive Solution

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }

    private void postorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // Traverse left subtree
        postorderHelper(node.left, result);
        // Traverse right subtree
        postorderHelper(node.right, result);
        // Visit the root node
        result.add(node.val);
    }
}

Iterative Solution

import java.util.*;

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        return result;
    }
}

Complexity Analysis

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once.

The space complexity for the recursive solution is O(h), where h is the height of the tree, due to the call stack. For the iterative solution, the space complexity is also O(h) due to the stack used for traversal.

Edge Cases

Consider the following edge cases:

An empty tree (root is null) - The output should be an empty list.
A tree with only one node - The output should be a list with that single node's value.
A tree with only left or right subtrees - Ensure the traversal order is correct.

Testing

To test the solution comprehensively, consider the following test cases:

Empty tree: []
Single node tree: [1]
Tree with only left children: [3, 2, 1]
Tree with only right children: [3, 2, 1]
Balanced tree: [left subtree, right subtree, root]

Thinking and Problem-Solving Tips

When approaching tree traversal problems, it is helpful to:

Understand the different types of tree traversals (preorder, inorder, postorder).
Draw the tree and manually perform the traversal to understand the order.
Consider both recursive and iterative solutions and understand their trade-offs.

Conclusion

Postorder tree traversal is a fundamental problem that helps in understanding tree data structures and their traversals. By practicing both recursive and iterative approaches, you can improve your problem-solving skills and be better prepared for similar problems.

Additional Resources

For further reading and practice, consider the following resources: