Binary Tree Postorder Traversal

EasyTrees · Post-order Traversal🧩 Tree DFS LeetCode #145 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, return its node values in post-order: for every node, all of its left subtree first, then all of its right subtree, and only then the node itself. An empty tree gives an empty list.

Inputroot = [1,null,2,3]Output[3,2,1]

Inputroot = [1,2,3,4,5]Output[4,5,2,3,1]

Inputroot = []Output[]

0 ≤ n ≤ 100 · -100 ≤ Node.val ≤ 100 · Follow-up: recursion is trivial — can you do it iteratively?

Try it yourself

Java

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A node may be emitted only after both children are finished. When you are back at a node, the question is “did I come from the left or the right?” — track the last visited node to tell.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecursive DFS

Time O(n)Space O(h)

Follow the definition: recurse left, recurse right, then add the node. Each node is visited once; the call stack grows to the tree height h (n when the tree is a chain).

Java

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, res);
    return res;
}

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

Trivial and correct, but deep trees can overflow the call stack.

BetterOne Stack + Last-Visited Pointer

Time O(n)Space O(h)

Dive down left spines as in in-order, but only peek the top. If it has an unvisited right child, go there; otherwise both subtrees are done, so pop and emit it. last distinguishes “returning from the right” from “right not yet explored”.

Java

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root, last = null;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode top = stack.peek();
        if (top.right != null && top.right != last) {
            curr = top.right;          // right subtree still to do
        } else {
            res.add(top.val);          // both subtrees finished
            last = stack.pop();
        }
    }
    return res;
}

Iterative, stack bounded by height — the standard follow-up answer.

OptimalMorris Post-order (Reverse Right Edges)

Time O(n)Space O(1)

Hang the tree under a dummy node and thread predecessors as in Morris in-order. When a thread to curr is found again, its left subtree is finished: output the right-edge path from curr.left to the predecessor in reverse. Each node lies on exactly one such path, so reversing costs O(n) total.

Java

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode curr = new TreeNode(0, root, null); // dummy parent
    while (curr != null) {
        if (curr.left == null) {
            curr = curr.right;
            continue;
        }
        TreeNode pred = curr.left;
        while (pred.right != null && pred.right != curr) pred = pred.right;
        if (pred.right == null) {      // first visit: thread and go left
            pred.right = curr;
            curr = curr.left;
        } else {                       // left subtree done: emit its right edge
            pred.right = null;
            int start = res.size();
            for (TreeNode n = curr.left; n != null; n = n.right) res.add(n.val);
            Collections.reverse(res.subList(start, res.size()));
            curr = curr.right;
        }
    }
    return res;
}

O(1) extra space (besides output); trickiest to write, tree restored afterwards.

Pro tip

Shortcut: a root → right → left pre-order, reversed, is exactly post-order (the “two stacks” trick), but it needs O(n) extra memory.

At a glance

Level	Approach	Time	Space
Brute Force	Recursive DFS	`O(n)`	`O(h)`
Better	One Stack + Last-Visited Pointer	`O(n)`	`O(h)`
Optimal	Morris Post-order (Reverse Right Edges)	`O(n)`	`O(1)`

Common pitfalls

Popping as soon as the left spine ends — that emits in-order, not post-order.
Without last, the loop re-enters the right subtree forever.
Morris: not removing the thread before walking the right edge — loops back to curr.

Interview tips

Explain why post-order is the hardest iterative traversal: the node is seen twice.
Offer the reverse-pre-order trick as a quick alternative, then the one-stack version.
Mention post-order's use: freeing trees, subtree sums/heights, bottom-up DP.

Pattern

Post-order (children before parent) → bottom-up tree computations like height, diameter, subtree sums.

My notes saved in this browser