Algocademy Logo

Post Order Tree Traversal 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, 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.

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 function that recursively visits the left subtree, then the right subtree, and finally processes 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 Approach

  1. Define a helper function that takes a node and a result array.
  2. If the node is null, return.
  3. Recursively call the helper function on the left child.
  4. Recursively call the helper function on the right child.
  5. Push the node's value to the result array.

Iterative Approach

  1. Initialize two stacks: one for traversal and one for storing the postorder result.
  2. Push the root node to the first stack.
  3. While the first stack is not empty:
    • Pop a node from the first stack and push it to the second stack.
    • Push the left child of the popped node to the first stack (if it exists).
    • Push the right child of the popped node to the first stack (if it exists).
  4. Pop all nodes from the second stack and add their values to the result array.

Code Implementation

Recursive Solution

// Recursive postorder traversal
function postorderTraversal(root) {
    const result = [];
    function traverse(node) {
        if (!node) return;
        traverse(node.left);  // Visit left subtree
        traverse(node.right); // Visit right subtree
        result.push(node.val); // Visit root
    }
    traverse(root);
    return result;
}

Iterative Solution

// Iterative 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);   // Push left child to stack1
        if (node.right) stack1.push(node.right); // Push right child to stack1
    }
    
    while (stack2.length) {
        const node = stack2.pop();
        result.push(node.val); // Collect nodes in postorder
    }
    
    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 O(n) due to the use of two stacks.

Edge Cases

Consider the following edge cases:

Testing

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

Thinking and Problem-Solving Tips

When approaching tree traversal problems, it's helpful to understand the different types of traversals (preorder, inorder, postorder) and their applications. Practice by solving similar problems and implementing both recursive and iterative solutions to strengthen your understanding.

Conclusion

Postorder tree traversal is a fundamental problem in computer science with various applications. Understanding both recursive and iterative approaches is crucial for solving more complex tree-related problems. Practice and familiarity with different traversal techniques will improve your problem-solving skills.

Additional Resources