Skip to main content
CodePeetCodePeet
CodePeet 250

Binary Tree Postorder Traversal

EASYProblemSolveExternal Links

Description

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

In postorder traversal, you visit nodes in the following order for every subtree:

  1. First, completely traverse the left subtree
  2. Then, completely traverse the right subtree
  3. Finally, visit the current node itself

This is often remembered as Left → Right → Root. The result should be a list of all node values in the order they are visited during this traversal.

Examples

Example 1

Input: root = [1, null, 2, 3]

The tree looks like:

  1
   \
    2
   /
  3

Output: [3, 2, 1]

Explanation: Following postorder (Left → Right → Root):

  • Start at node 1. It has no left child, so go to the right subtree (rooted at 2).
  • At node 2, go to its left child first: node 3.
  • Node 3 has no children, so visit node 3. Result so far: [3].
  • Back at node 2, its left subtree is done and it has no right child. Visit node 2. Result: [3, 2].
  • Back at node 1, its right subtree is done. Visit node 1. Result: [3, 2, 1].

Example 2

Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]

The tree looks like:

        1
       / \
      2    3
     / \    \
    4   5    8
       / \  /
      6   7 9

Output: [4, 6, 7, 5, 2, 9, 8, 3, 1]

Explanation: Postorder visits all descendants before the node itself. Starting from the deepest left, we get leaves 4, then 6, 7 (children of 5), then 5, then 2 (parent of 4 and 5), then 9 (child of 8), then 8, then 3, and finally root 1.

Example 3

Input: root = []

Output: []

Explanation: An empty tree has no nodes to visit, so the traversal result is an empty list.

Example 4

Input: root = [1]

Output: [1]

Explanation: A single-node tree has no left or right subtrees. The only action is to visit the root itself, yielding [1].

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 ≤ Node.val ≤ 100

Editorial

Brute Force

Intuition

The most natural way to perform postorder traversal is using recursion, because the traversal definition itself is recursive: to postorder-traverse a tree, first postorder-traverse its left subtree, then its right subtree, then visit the root.

Think of it like cleaning a house room by room. Before you can declare a room "done" (visit the node), you need to make sure every room connected to its left hallway is done, then every room connected to its right hallway is done, and only then mark the current room as finished.

We write a recursive function that:

  1. Returns immediately if the node is null (base case)
  2. Calls itself on the left child
  3. Calls itself on the right child
  4. Appends the current node's value to the result

This directly mirrors the Left → Right → Root ordering.

Step-by-Step Explanation

Let's trace through Example 1: root = [1, null, 2, 3]

Tree:

  1
   \
    2
   /
  3

Step 1: Call postorder(node 1). Node 1 is not null. Recurse on left child first.

Step 2: Call postorder(null) — node 1's left child is null. Return immediately. No value added.

Step 3: Back at node 1, left subtree done. Now recurse on right child: call postorder(node 2).

Step 4: At node 2, recurse on left child first: call postorder(node 3).

Step 5: At node 3, recurse on left child: call postorder(null). Return immediately.

Step 6: At node 3, left done. Recurse on right child: call postorder(null). Return immediately.

Step 7: At node 3, both children done. Visit node 3 → append 3 to result. Result: [3].

Step 8: Back at node 2, left subtree done. Recurse on right child: call postorder(null). Return immediately.

Step 9: At node 2, both children done. Visit node 2 → append 2 to result. Result: [3, 2].

Step 10: Back at node 1, right subtree done. Visit node 1 → append 1 to result. Result: [3, 2, 1].

Recursive Postorder Traversal on [1, null, 2, 3] — Watch how recursion dives to the deepest left, then right, and visits each node only after both subtrees are fully processed.

Algorithm

  1. If the current node is null, return (base case).
  2. Recursively call the function on the left child.
  3. Recursively call the function on the right child.
  4. Append the current node's value to the result list.
  5. Return the result list after the initial call completes.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode* node, vector<int>& result) {
        if (node == nullptr) return;
        traverse(node->left, result);
        traverse(node->right, result);
        result.push_back(node->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;
    }
};
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def traverse(node):
            if node is None:
                return
            traverse(node.left)
            traverse(node.right)
            result.append(node.val)

        traverse(root)
        return result
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List<Integer> result) {
        if (node == null) return;
        traverse(node.left, result);
        traverse(node.right, result);
        result.add(node.val);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every node in the tree exactly once. At each node we do O(1) work (one append operation). With n nodes total, this gives O(n) time.

Space Complexity: O(h), where h is the height of the tree

The space is consumed by the recursion call stack. In the worst case (a completely skewed tree where every node has only one child), h = n, making the space O(n). In the best case (a balanced tree), h = log n, giving O(log n) space. The result list itself takes O(n) space but is typically not counted as auxiliary space since it is the required output.

Why This Approach Is Not Efficient

The recursive approach is elegant and correct, but it has a fundamental limitation: it relies on the system call stack to manage the traversal state.

For a skewed tree with n = 100 nodes (all nodes forming a single chain), the recursion depth reaches 100. While this is fine for the given constraints, in general:

  1. Stack overflow risk: Deep recursion on very large or unbalanced trees can exceed the system's stack size limit, causing a stack overflow crash.
  2. No explicit control over traversal: With recursion, we cannot easily pause, resume, or step through the traversal — the function call stack manages everything implicitly.
  3. Interview expectation: The problem's follow-up explicitly asks: "Could you do it iteratively?" — signaling that converting this to an iterative solution using an explicit stack is the expected next step.

The core insight for improvement is: we can replace the implicit recursion stack with an explicit stack data structure, giving us the same O(n) time but with direct control over the traversal process and no risk of stack overflow.

Better Approach - Iterative with Two Stacks

Intuition

Postorder is Left → Right → Root. If we reverse this, we get Root → Right → Left. Notice that this reversed order is very similar to preorder (Root → Left → Right), except the left and right children are swapped.

Here is the key insight: if we perform a modified preorder traversal where we visit the right child before the left child (giving us Root → Right → Left), and collect the results, then reversing that collection gives us Left → Right → Root — which is exactly postorder!

Instead of reversing at the end, we can use a second stack. We push each node we "visit" onto a second stack. Since a stack is LIFO (last-in, first-out), popping everything from the second stack at the end automatically reverses the order.

Think of it like recording a video in reverse: you film the scenes in Root → Right → Left order, then play the tape backwards to get Left → Right → Root.

Step-by-Step Explanation

Let's trace through with this tree:

  1
   \
    2
   /
  3

Step 1: Push root (node 1) onto stack1.

  • Stack1: [1]
  • Stack2: []

Step 2: Pop node 1 from stack1. Push it onto stack2. Push its left child (null → skip) and right child (node 2) onto stack1.

  • Stack1: [2]
  • Stack2: [1]

Step 3: Pop node 2 from stack1. Push it onto stack2. Push its left child (node 3) onto stack1. Right child is null → skip.

  • Stack1: [3]
  • Stack2: [1, 2]

Step 4: Pop node 3 from stack1. Push it onto stack2. No children to push.

  • Stack1: []
  • Stack2: [1, 2, 3]

Step 5: Stack1 is empty. Pop all from stack2: 3, 2, 1.

Result: [3, 2, 1]

Two-Stack Iterative Postorder Traversal — Watch how we simulate a reversed preorder (Root → Right → Left) using stack1, collect nodes in stack2, then read stack2 top-to-bottom to get postorder.

Algorithm

  1. Create two empty stacks: stack1 and stack2.
  2. Push the root node onto stack1.
  3. While stack1 is not empty:
    a. Pop a node from stack1 and push it onto stack2.
    b. If the popped node has a left child, push it onto stack1.
    c. If the popped node has a right child, push it onto stack1.
  4. Pop all elements from stack2 one by one — this sequence is the postorder traversal.

Code

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<TreeNode*> stack1, stack2;
        stack1.push(root);

        while (!stack1.empty()) {
            TreeNode* node = stack1.top();
            stack1.pop();
            stack2.push(node);

            if (node->left) stack1.push(node->left);
            if (node->right) stack1.push(node->right);
        }

        while (!stack2.empty()) {
            result.push_back(stack2.top()->val);
            stack2.pop();
        }

        return result;
    }
};
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        stack1 = [root]
        stack2 = []

        while stack1:
            node = stack1.pop()
            stack2.append(node)

            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)

        result = []
        while stack2:
            result.append(stack2.pop().val)

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

        Deque<TreeNode> stack1 = new ArrayDeque<>();
        Deque<TreeNode> stack2 = new ArrayDeque<>();
        stack1.push(root);

        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);

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

        while (!stack2.isEmpty()) {
            result.add(stack2.pop().val);
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is pushed and popped from stack1 exactly once, and pushed and popped from stack2 exactly once. That is 4 constant-time operations per node, giving O(n) total.

Space Complexity: O(n)

Both stacks combined can hold up to n nodes. In the worst case, stack2 always holds all n nodes when the loop finishes. This is O(n) extra space. Compared to the recursive approach (which uses O(h) stack space), this uses more space when h < n (balanced trees), but avoids the risk of call stack overflow.

Why This Approach Is Not Efficient

The two-stack approach works correctly and eliminates recursion, but it uses O(n) space for the second stack regardless of the tree shape. Even for a perfectly balanced tree (where recursion would only use O(log n) space), the two-stack method still stores all n nodes in stack2.

The key inefficiency: we collect ALL nodes before producing any output. We cannot start outputting results until the entire tree is traversed.

Can we do better? Yes — using a single stack, we can achieve the same O(n) time while using only O(h) space (matching the recursive approach's space usage) and producing results on the fly. The trick is to track which direction we came from (did we just finish the left subtree or the right subtree?) to decide whether to visit the node or continue to the right subtree.

Optimal Approach - Iterative with One Stack

Intuition

The challenge with postorder traversal iteratively is knowing when it is safe to process a node. In preorder or inorder, the decision is simpler. But in postorder, we must ensure both subtrees are done before visiting the parent.

The single-stack approach uses a clever trick: we maintain a pointer called lastVisited that remembers the most recently visited (outputted) node. When we peek at the top of the stack, we check:

  1. Does this node have a right child that has NOT been visited yet? If yes, we need to go right before we can visit this node. Push the right child and continue.
  2. Is the right child null or already visited? Then both subtrees are done, and we can safely visit (output) this node.

Think of it like a checklist at each node:

  • ✅ Left subtree done? (We handled this by always pushing left children first)
  • ✅ Right subtree done? (We check via lastVisited)
  • If both are checked, visit the node and mark it as lastVisited.

Step-by-Step Explanation

Let's trace through with the same tree:

  1
   \
    2
   /
  3

Step 1: Initialize: current = node 1, stack = [], lastVisited = null.

Step 2: current (node 1) is not null → push node 1 onto stack, move to left child.

  • Stack: [1], current = null.

Step 3: current is null. Peek at stack top → node 1. Check right child: node 2 exists and lastVisited ≠ node 2. So we must process right subtree first. Set current = node 2.

Step 4: current (node 2) is not null → push node 2 onto stack, move to left child.

  • Stack: [1, 2], current = node 3.

Step 5: current (node 3) is not null → push node 3 onto stack, move to left child.

  • Stack: [1, 2, 3], current = null.

Step 6: current is null. Peek at stack top → node 3. Right child is null → safe to visit. Pop node 3, output 3, set lastVisited = node 3.

  • Stack: [1, 2], result: [3].

Step 7: current is still null. Peek at stack top → node 2. Right child is null, so right subtree is done. Pop node 2, output 2, set lastVisited = node 2.

  • Stack: [1], result: [3, 2].

Step 8: current is still null. Peek at stack top → node 1. Right child is node 2. Is lastVisited == node 2? YES → right subtree done. Pop node 1, output 1, set lastVisited = node 1.

  • Stack: [], result: [3, 2, 1].

Step 9: Stack is empty and current is null → traversal complete.

Result: [3, 2, 1]

One-Stack Iterative Postorder with lastVisited Tracking — Watch how the single stack pushes nodes going left, then checks the lastVisited pointer to determine if the right subtree is done before visiting a node.

Algorithm

  1. Initialize an empty stack, set current = root, and lastVisited = null.
  2. Loop while the stack is not empty OR current is not null:
    a. If current is not null:
    • Push current onto the stack.
    • Set current = current.left (go left).
      b. Else (current is null — reached a dead end):
    • Peek at the top of the stack (call it peekNode).
    • If peekNode.right is not null AND peekNode.right ≠ lastVisited:
      • Set current = peekNode.right (go right — right subtree not done yet).
    • Else:
      • Pop peekNode from the stack.
      • Append peekNode.val to the result.
      • Set lastVisited = peekNode.
  3. Return the result list.

Code

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* current = root;
        TreeNode* lastVisited = nullptr;

        while (!stk.empty() || current != nullptr) {
            if (current != nullptr) {
                stk.push(current);
                current = current->left;
            } else {
                TreeNode* peekNode = stk.top();
                if (peekNode->right != nullptr && peekNode->right != lastVisited) {
                    current = peekNode->right;
                } else {
                    stk.pop();
                    result.push_back(peekNode->val);
                    lastVisited = peekNode;
                }
            }
        }

        return result;
    }
};
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        last_visited = None

        while stack or current:
            if current:
                stack.append(current)
                current = current.left
            else:
                peek_node = stack[-1]
                if peek_node.right and peek_node.right != last_visited:
                    current = peek_node.right
                else:
                    stack.pop()
                    result.append(peek_node.val)
                    last_visited = peek_node

        return result
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        TreeNode lastVisited = null;

        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode peekNode = stack.peek();
                if (peekNode.right != null && peekNode.right != lastVisited) {
                    current = peekNode.right;
                } else {
                    stack.pop();
                    result.add(peekNode.val);
                    lastVisited = peekNode;
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is pushed onto the stack exactly once and popped exactly once. The peek operation at each iteration is O(1). While some nodes may be peeked at twice (once before going right, once after), the total number of operations is still proportional to n. Hence O(n) overall.

Space Complexity: O(h), where h is the height of the tree

The stack holds at most the nodes along a single root-to-leaf path at any given time. For a balanced tree, h = log n, so space is O(log n). For a skewed tree, h = n, so worst case is O(n). This matches the space efficiency of the recursive solution but avoids system call stack limitations.