Binary Tree Postorder Traversal

LeetCode 145 • Easy • Trees

Input: root = [1,2,3,4,5] → Output: [4,5,2,3,1]
Iterative trick: root-right-left stack walk, then ans[::-1] (left-right-root).

TimeO(n)visit each node

SpaceO(n)stack + ans

Stack: []Ans: []

Current

In Stack

In Ans

Stack

empty

Ans

[]

Speed:

Ready

Press Play. One stack: pop, append, push left then right. Reverse at end.

✎ Whiteboard

Size:3

⌨ Type It

Interview follow-up: iterative postorder without recursion. Reverse preorder (root-right-left).

═══ POSTORDER — ITERATIVE ONE STACK ═══

PATTERN ▸ root-right-left stack, reverse O(n)

① INIT

stack = [root]; ans = []

② LOOP

node = stack.pop(); ans.append(node.val)

push left, then right (right pops first)

③ REVERSE

return ans[::-1]

▼ your implementation ▼

Verify your solution: