Start learning free

LESSON 192 OF 321 · BINARY TREES

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

Practice O(n) Read the full explanation

You get the root of a binary tree. Return an array of its node values in postorder.

In postorder, each node comes after its two subtrees. Its left subtree comes first. Then comes its right subtree. The node itself comes last.

Trees are written level by level, from top to bottom and left to right. A null marks a missing child.

Example 1:

Input: [5,3,8,1,4,null,9]
     5
    / \
   3   8
  / \   \
 1   4   9

Output: [1,4,3,9,8,5]

Example 2:

Input: [9,6,null,null,2]
     9
    /
   6
    \
     2

Output: [2,6,9]
Explanation: Each node here has only one child.
The child still comes before its parent.

Example 3:

Input: [7]
Output: [7]

Constraints:

  • 1 to 1,000 nodes.
  • Each value is a whole number from 1 to 1,000.
  • No two nodes have the same value.

Follow up: The recursive version is only a few lines. Can you also write it without recursion, with your own stack?

STEP 1 OF 6
    Ctrl + Enter to check

    JAVASCRIPT · BINARY TREES

    Post Order Tree Traversal in JavaScript, explained

    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:

    • An empty tree (root is null): The output should be an empty array.
    • A tree with only one node: The output should be an array with that single node's value.

    Testing

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

    • Empty tree: postorderTraversal(null) should return [].
    • Single node tree: postorderTraversal({val: 1, left: null, right: null}) should return [1].
    • Tree with multiple nodes: postorderTraversal({val: 1, left: null, right: {val: 2, left: {val: 3, left: null, right: null}, right: null}}) should return [3, 2, 1].

    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

    Keep going with JavaScript1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free