Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes' values — visit the left subtree, then the right subtree, then the node last.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Postorder means the left subtree, then the right subtree, then the node.

Recursively that's three lines with the node recorded last.

Iteratively, run a node-right-left stack walk and reverse the result.

Common doubts

Those values depend on the children's results, and postorder guarantees both subtrees are fully processed before the parent.

The reverse of the sequence (node, right, left) is (left, right, node), which is exactly the postorder definition.

O(height) recursively; the reversed-walk version uses O(n) for the output list it reverses.

Interview follow-ups

· What an interviewer asks next.

Track a lastVisited pointer: only pop and record a node once its right child has been visited, otherwise descend right first.

You must free both children before the parent, so you delete in left-right-node order — postorder.

Fun facts

Postorder is how a compiler evaluates an expression tree: operands (children) before the operator (parent).
Reverse-Polish notation is exactly the postorder traversal of an expression tree.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

Input: root = [1, null, 2, 3]
Output: [3, 2, 1]
Left subtree (empty), then the right subtree yielding 3 then 2, then the root 1 last.

Example 2

Input: root = []
Output: []
An empty tree has no nodes.

Constraints

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

Postorder means left, right, node — a node is recorded only after both its subtrees are done. The recursive version is a direct transcription. The neat iterative trick: do a modified preorder that visits node, right, left, then reverse the whole thing — the reverse of (node, right, left) is exactly (left, right, node).

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Recursion / stack. Postorder is the natural order for computing a value that depends on both children first.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The order

“What is postorder exactly?”

The left subtree, then the right subtree, then the current node.

“Why is postorder useful?”

Anything that needs child results before the parent — deleting a tree, computing height, path sums.

The ideal opening — say it like this

Postorder is left, right, node, so I recurse into both subtrees before recording the node.

Iteratively I run a node-right-left walk with a stack and reverse the result — that reversal turns it into left-right-node.

Understand the problem

Worked example — tree [1, null, 2, 3] (1 with right child 2, whose left child is 3)

        1
         \
          2
         /
        3
postorder: left of 1 (none) -> right subtree of 1 -> 1
           in that subtree: 3 -> 2
result: [3, 2, 1]

Key observations

1Aha

Postorder is left, right, node

The node comes last, after both subtrees — which is why it's the order for bottom-up computations.

2Aha

Reverse a node-right-left walk

A stack-based node-right-left walk, reversed, is postorder — the cleanest iterative version.

3Aha

Linear time and height space

Every node is visited once (O(n)); the stack holds at most O(height) nodes.

Brute force vs optimal

	Iterative (reversed node-right-left)	Recursive
Idea	Walk node-right-left with a stack, reverse	dfs(left); dfs(right); record
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n) time; the recursive form is the clearest. Full code is in the Approaches selector below.

Summary

Key takeaway

Postorder = left, right, node. Recurse both subtrees before recording the node — or run a node-right-left stack walk and reverse it. O(n) time, O(height) space recursively.

postorder(node):
    if node is null: return
    postorder(node.left)
    postorder(node.right)
    visit(node)