Free lesson · DSA Mastery - Interview Prep, End to End

Binary Tree Postorder Traversal

Medium8 min readdsabinary-tree

Binary Tree Postorder Traversal

Binary Tree Postorder Traversal opens the Post Order sub-group with the left-right-node traversal: recurse into the left subtree, then the right, then visit the current node last. This is the order for bottom-up aggregation - when a node's answer depends on results already computed from its children (heights, sums, validity flags). We present three forms, like the other traversal openers: the trivial recursion, the iterative stack version (with the classic "reverse a modified preorder" trick), and Morris traversal for O(1) extra space.

The insight: postorder visits a node only after both its subtrees are fully processed, so the node can combine its children's results. The recursion expresses this by placing the visit after both recursive calls. The slickest iterative version exploits a symmetry: a node-right-left traversal (a mirrored preorder) reversed gives left-right-node - postorder. Morris postorder is the most intricate of the three, reversing partial chains along threads.

The Problem

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

Example 1:

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

Example 2:

Input:  root = []
Output: []

Example 3:

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

Constraints:

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

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Recursion	O(n)	O(h)	Simplest
2	Iterative (reverse modified preorder)	O(n)	O(h)	Answers the follow-up
3	Morris traversal	O(n)	O(1) extra	Constant space

All visit every node once - O(n). Recursion is trivial but uses O(h) stack. The iterative "node-right-left then reverse" version is the cleanest follow-up answer (an honest two-stack or single-stack-plus-reverse variant). Morris postorder achieves O(1) extra space but is notably more involved than its preorder/inorder cousins.

Approach 1: Recursion - Simplest

The Idea

Recurse left, recurse right, then record the node's value. The "node after both recursions" placement is what makes it postorder.

Logic Flowchart

graph TD
    A["postorder(node)"] --> B{"node == null?"}
    B -->|Yes| C["return"]
    B -->|No| D["postorder(left)"]
    D --> E["postorder(right)"]
    E --> F["visit node (record val)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows recursive postorder. We recurse into the left subtree, then the right subtree, and only then record the current node's value.

Code

public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
}

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

This Java code recurses into the left subtree, then the right subtree, then records the current node's value, producing left-right-node order.

Complexity

Time: O(n). Space: O(h) recursion stack.

Approach 2: Iterative (Reverse Modified Preorder) - Answers the Follow-up

The Idea

Postorder is left-right-node. Its reverse is node-right-left - which is a preorder variant that visits the right child before the left. So run that mirrored preorder with a stack (push left before right, so right pops first), collecting values, then reverse the collected list to get postorder. Simple and reliable.

Logic Flowchart

graph TD
    A["if root null: return []; stack = [root]; out = []"] --> B{"stack not empty?"}
    B -->|No| C["reverse(out); return out"]
    B -->|Yes| D["node = pop; out.add(node.val)"]
    D --> E["push left child (if any)"]
    E --> F["push right child (if any)"]
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the reverse-preorder method. We perform a node-right-left traversal by pushing the left child before the right, collecting values, then reverse the collection to obtain postorder.

Code

public static List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.addFirst(node.val);                 // prepend → builds reverse order directly
        if (node.left != null) stack.push(node.left);   // push left first
        if (node.right != null) stack.push(node.right); // so right pops first (node-right-left)
    }
    return out;
}

// Usage:
// postorderTraversal([1,null,2,3]) -> [3,2,1]

This Java code pops nodes in node-right-left order, prepending each value to the output so it ends up in left-right-node order, equivalent to reversing a mirrored preorder.

Step-by-Step Walkthrough

A frame-by-frame trace on root = [1,null,2,3] (1 has right child 2; 2 has left child 3):

graph LR
    F0["stack=[1]; pop 1, addFirst → out=[1]; push left(none), right 2. stack=[2]"]
    F1["pop 2, addFirst → out=[2,1]; push left 3, right(none). stack=[3]"]
    F2["pop 3, addFirst → out=[3,2,1]; no children"]
    F3["return [3,2,1]"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traverses one with a right child two, which has a left child three. Prepending each popped value builds three, two, one, the postorder.

Result: [3,2,1].

Complexity

Time: O(n). Space: O(h) stack.

Approach 3: Morris Traversal - Constant Space

The Idea

Morris postorder is the most intricate variant. Use a dummy root whose left child is the real root. For each node with a left child, thread the in-order predecessor to it as usual; when the thread is found already set (left subtree finished), reverse the chain of right-pointers from the left child to the predecessor, record those nodes in order, then reverse it back and unthread. This careful reversal of partial chains emits nodes in postorder using O(1) extra space.

Logic Flowchart

graph TD
    A["dummy.left = root; cur = dummy"] --> B{"cur != null?"}
    B -->|No| C["return result"]
    B -->|Yes| D{"cur.left == null?"}
    D -->|Yes| E["cur = cur.right"]
    D -->|No| F["pred = rightmost of cur.left"]
    F --> G{"pred.right == null?"}
    G -->|Yes| H["pred.right = cur; cur = cur.left"]
    G -->|No| I["reverse-add chain cur.left..pred; pred.right = null; cur = cur.right"]
    E --> B
    H --> B
    I --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Morris postorder. Using a dummy root and threading, when a left subtree is finished we reverse the chain of right pointers from the left child to the predecessor, record those nodes, then restore the chain and unthread, all in constant extra space.

Code

public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode dummy = new TreeNode(0);
    dummy.left = root;
    TreeNode cur = dummy;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;            // thread
                cur = cur.left;
            } else {
                addReverse(cur.left, pred, result);  // emit chain in postorder
                pred.right = null;           // unthread
                cur = cur.right;
            }
        }
    }
    return result;
}

private static void addReverse(TreeNode from, TreeNode to, List<Integer> result) {
    int count = 0;
    TreeNode node = from;
    while (true) { count++; if (node == to) break; node = node.right; }  // length
    int start = result.size();
    node = from;
    for (int i = 0; i < count; i++) { result.add(node.val); node = node.right; }
    // reverse the just-added segment so it reads bottom-up (postorder)
    for (int i = start, j = result.size() - 1; i < j; i++, j--) {
        int tmp = result.get(i); result.set(i, result.get(j)); result.set(j, tmp);
    }
}

This Java code performs Morris postorder using a dummy root. When a left subtree completes, it appends the chain from the left child to the predecessor and reverses that segment so the nodes appear in postorder, then restores the thread, using constant extra space aside from the output.

Complexity

Time: O(n) (each edge handled a constant number of times). Space: O(1) extra.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Recursion	O(n)	O(h)	Left, right, node	Simplest
Iterative reverse-preorder	O(n)	O(h)	Mirror preorder, then reverse	Follow-up answer
Morris	O(n)	O(1) extra	Threading with chain reversal	Constant space required

All are O(n) time. Recursion is cleanest to write; the reverse-modified-preorder is the most practical follow-up (no fragile bookkeeping); Morris is the O(1)-space option but is the trickiest of the three traversal orders to implement correctly. In interviews, the reverse-preorder trick is usually the best answer to "do postorder iteratively."

Variations & Follow-ups

Why does reversing a node-right-left traversal give postorder?

Node-right-left is the exact reverse of left-right-node. If you list nodes in node-right-left order and then reverse the list, you get left-right-node - which is postorder. Node-right-left is itself just preorder with the children swapped, easily done with a single stack (push left before right so right is processed first). Prepending each visited value (instead of appending then reversing) builds the postorder directly. This trick sidesteps the awkward "have I finished both children?" tracking that a literal iterative postorder needs.

Why is a literal single-stack postorder harder than preorder/inorder?

In postorder you must visit a node only after both its subtrees, so when you return to a node you need to know whether you're coming up from the left subtree (go right next) or the right subtree (visit the node now). That requires tracking a "last visited" node or a per-node state flag - extra bookkeeping that preorder and inorder don't need. The reverse-preorder trick avoids this entirely, which is why it's the preferred iterative method.

Why is postorder the order for bottom-up problems?

Many tree problems compute a node's answer from its children's answers - a node's height is 1 + max(child heights), its subtree sum is node.val + child sums, its validity depends on both subtrees being valid. Postorder guarantees both children are fully processed before the node, so the combination step always has its inputs ready. This "children first, then combine" order is exactly what bottom-up aggregation requires, and it's why this sub-group's problems are postorder.

When would you actually need Morris postorder?

Only when O(1) extra space is a hard requirement and you need postorder specifically - a rare combination. Morris postorder's chain-reversal bookkeeping makes it error-prone, so unless the constraint demands it, the recursive or reverse-preorder approach is preferred. Knowing it exists (and that all three traversals have an O(1)-space Morris form) is worthwhile, but reaching for it should be deliberate.

What about edge cases?

Empty tree (Example 2): Empty result.
Single node: [root.val].
Left-skewed chain: Visited bottom-to-top.
Right-skewed chain: Deepest node first, root last.

Common Interview Pitfalls

Recording before both recursions. Postorder visits the node last; recording earlier gives pre/inorder.
Forgetting to reverse (or prepend). The mirrored-preorder collection must be reversed to become postorder.
Push order in the iterative version. For node-right-left, push left before right so right pops first.
Morris: not restoring threads. Leaving threads in place corrupts the tree and risks infinite loops.

Why This Topic Matters

Binary Tree Postorder Traversal establishes the node-last, bottom-up order and three ways to realize it - including the elegant reverse-modified-preorder trick that is the go-to iterative answer. Postorder is the foundation for every remaining problem in this sub-group, because each computes a node's result from its children. Internalizing "children before node" is what makes heights, diameters, LCA, and max-path-sum fall out naturally.

The next topic, Invert Binary Tree, is the gentlest postorder application (and a famously iconic interview question): produce the mirror image of a tree by swapping every node's left and right children. The recursion is naturally bottom-up - invert the left subtree, invert the right subtree, then swap the two child pointers at the node - though it works in any order since the swap is independent per node. It's a light, confidence-building start to the sub-group before the aggregation problems (diameter, balanced-height, path sums) put the postorder return-value pattern to serious work.

Back to DSA Mastery - Interview Prep, End to End