LeetCode 145 – Binary Tree Postorder Traversal

Postorder is the hardest of the three traversals to write iteratively — and the standard interview answer avoids writing it at all. There is a trick that turns it into preorder with two lines changed. Knowing both that trick and the honest version, and knowing when each is appropriate, is what this problem is for.

The problem

Return the postorder traversal: left subtree, right subtree, then the node.

    1
     \          -> [3, 2, 1]
      2
     /
    3

    4
   / \        -> [1, 3, 2, 5, 7, 6, 4]
  2   6
 / \ / \
1  3 5  7        the root is always LAST

[]   -> []
[1]  -> [1]

The root coming last is the defining property, and it is what makes postorder the traversal for anything that must process children before parents — freeing a tree, computing subtree sizes, evaluating an expression tree.

Why it is awkward

In preorder a node is emitted on arrival and immediately forgotten. In postorder a node must be kept until both subtrees are done, so on popping it you cannot tell whether you are arriving for the first time or returning from the right subtree.

The honest fix is to track that state — a visited flag per node, or a "last node emitted" pointer compared against the current node's right child. Both work and both are fiddly under time pressure.

The reversal trick

Look at the orders written out:

postorder                 left,  right, node
reverse it                node,  right, left
that is preorder with the children swapped!

So: run the preorder loop, push left before right instead of right before left, and reverse the result. Every awkwardness disappears, because the modified traversal still emits each node on arrival.

tree 4(2(1,3), 6(5,7))

node-right-left:  4, 6, 7, 5, 2, 3, 1
reversed:         1, 3, 2, 5, 7, 6, 4    = postorder

Java

class Solution {
    public 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();

            // Prepending turns node-right-left into left-right-node as we go,
            // so no separate reversal pass is needed.
            out.addFirst(node.val);

            // LEFT first here -- the mirror of preorder's right-first.
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        return out;
    }
}

LinkedList.addFirst is O(1), so prepending as you go replaces the reversal at no cost. Doing the same with ArrayList.add(0, x) would be O(n) per insert and quietly turn the whole traversal quadratic — the same trap as building a string by repeated prepending in Add Binary.

The declared type is LinkedList rather than List because addFirst is not on the List interface. Collecting into an ArrayList and calling Collections.reverse once at the end is equally good and arguably clearer.

Python

class Solution:
    def postorderTraversal(self, root: TreeNode) -> list[int]:
        if root is None:
            return []

        out, stack = [], [root]

        while stack:
            node = stack.pop()
            out.append(node.val)

            if node.left:                 # LEFT first -- mirror of preorder
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        return out[::-1]                  # node-right-left reversed IS postorder

Appending and reversing once at the end is O(n) total, which is why it is preferable to out.insert(0, ...) — that would be O(n) per element.

The honest version, for when it is asked for

Occasionally an interviewer wants genuine postorder without the reversal, usually because the traversal has to be streamed or interleaved with other work. The one-pointer form:

keep `lastVisited`
peek at the top of the stack
  if it has a right child that is NOT lastVisited -> descend right
  else -> pop, emit, lastVisited = it

Mention that this exists and what it costs. Producing the reversal trick and then saying "if you need it genuinely bottom-up rather than reversed at the end, that needs a lastVisited pointer" demonstrates you know the difference, which is more than most answers do.

Complexity

All linear. The reversal is a single extra O(n) pass, or free if you prepend into a list that supports it.

The three traversals together

Recursively they are one function with the visit line in three different places. Iteratively they are three different loops, and the reason is when a node can be emitted relative to its children. That single sentence explains the whole table.

What the interviewer is checking

• That you know postorder is reversed node-right-left.
• Push left before right — the mirror of preorder.
• That you prepend in O(1) or reverse once, never insert at index 0 in a loop.
• Empty tree and single node.
• That the root comes last, and why that matters for real uses.
• That you know a genuine bottom-up version exists and what it needs.