Binary Tree Postorder Traversal

Easy#145post-order

You get the root of a binary tree. Return its values in post-order: the left subtree, then the right subtree, then the node itself. Our tree: 4 with children 9 and 2; 9 has only a right child, 5; 2 has only a left child, 8 — the answer is [5, 9, 8, 2, 4].

145 Binary Tree Postorder TraversalWalkthrough · 1×

Example: the post-order of a binary tree, with one stack of our own instead of recursion. Each node has val, left and right.

nonenonenonenonenonenone49258out—stacktop on the right—
not reached yeton the stackcur, or node on top of the stackin out, #n is its placenone: an empty child

out = []: nothing is visited yet

01/66
restart · back · play · step
Speed
1function postorderTraversal(root):
2 out = []
3 stack = []
4 cur = root
5 last = none
6 while cur is not none or stack is not empty:
7 if cur is not none:
8 stack.push(cur)
9 cur = cur.left
10 else:
11 node = stack.top()
12 if node.right is not none and node.right is not last:
13 cur = node.right
14 else:
15 out.add(node.val)
16 last = stack.pop()
17 return out
state
cur
–
node
–
last
–
stack
–
out
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The stack holds the path from the root down to cur, like the calls of the recursive walk. A node leaves it only once both of its subtrees are in out.
  2. A node reaches the top of the stack twice when it has a right child: before its right subtree and after it. last is the node that went to out just before, so node.right is last means we are coming back.
  3. Without last, the second time would go right again and loop forever.

Complexity

Time O(n): every node is pushed and popped once, and seen on top at most twice. Memory O(h), where h is the height of the tree: the stack holds one path from the root down.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.