Post Order Tree Traversal II in JavaScript (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 (left-right-root) and return the values of the nodes in that order. Postorder traversal is significant in various applications such as expression tree evaluations, file system traversals, and more. A common pitfall is misunderstanding the traversal order or mishandling null nodes.

Approach

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

Naive Solution: Recursive Approach

The recursive approach is straightforward but not optimal for large trees due to potential stack overflow issues. Here’s a simple recursive solution:

function postorderTraversal(root) {
    const result = [];
    function traverse(node) {
        if (!node) return;
        traverse(node.left);
        traverse(node.right);
        result.push(node.val);
    }
    traverse(root);
    return result;
}

While this solution is easy to implement, it’s not suitable for the follow-up requirement of an iterative solution.

Optimized Solution: Iterative Approach

An iterative approach can be more efficient and avoids the risk of stack overflow. We can use two stacks to simulate the postorder traversal:

function postorderTraversal(root) {
    if (!root) return [];
    const stack1 = [root];
    const stack2 = [];
    const result = [];
    
    while (stack1.length) {
        const node = stack1.pop();
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    
    while (stack2.length) {
        result.push(stack2.pop().val);
    }
    
    return result;
}

This approach ensures that we traverse the tree in postorder without using recursion.

Algorithm

Here’s a step-by-step breakdown of the iterative algorithm:

Initialize two stacks: stack1 for processing nodes and stack2 for storing nodes in postorder.
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 node to stack1 if it exists.
- Push the right child of the node to stack1 if it exists.
While stack2 is not empty, pop nodes from stack2 and add their values to the result array.

Complexity Analysis

The time complexity of both the recursive and iterative solutions is O(n), where n is the number of nodes in the tree. The space complexity of the recursive solution is O(h) due to the call stack, where h is the height of the tree. The iterative solution has a space complexity of O(n) due to the use of two stacks.

Edge Cases

Consider the following edge cases:

An empty tree (should return an empty array).
A tree with only one node.
A tree with all nodes having only left or only right children.

Testing

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

console.log(postorderTraversal(null)); // []
console.log(postorderTraversal({ val: 1, left: null, right: null })); // [1]
console.log(postorderTraversal({ val: 1, left: { val: 2, left: null, right: null }, right: null })); // [2, 1]
console.log(postorderTraversal({ val: 1, left: null, right: { val: 2, left: { val: 3, left: null, right: null }, right: null } })); // [3, 2, 1]

Thinking and Problem-Solving Tips

When approaching tree traversal problems, it’s essential to understand the different traversal orders (preorder, inorder, postorder) and their applications. Practice solving similar problems and study various traversal algorithms to improve your problem-solving skills.

Conclusion

Postorder tree traversal is a fundamental problem in computer science with various applications. Understanding both recursive and iterative solutions is crucial for tackling more complex tree-related problems. Practice and explore further to master these concepts.

Additional Resources

For further reading and practice, consider the following resources: