Postorder traversal
Visit both children before the root — the order to use whenever a node's answer needs its children's answers first. About 8 minutes.
Left, then right, then root
Postorder of a tree means: do postorder on the left subtree, then on the right subtree, and only then write down the node's own value. "Post" means after, so the parent is recorded after both of its children.
It is like a teacher who will not record the class result until every student has handed in their work.
if not root:
return []
out = postorder_traversal(root.left)
out += postorder_traversal(root.right)
out.append(root.val)
return out- result
- [1]
Dive to the bottom-left first. 1 has no children, so it's done: visit it.
Why "children before parent" is useful
Some questions can only be answered once you already know the answer for both children. For example, "what is the sum of this subtree?" needs the left and right sums before it can add its own value.
Postorder guarantees both children are fully processed before their parent, so this kind of bottom-up work always has what it needs by the time it reaches the parent.
For the tree with root 5, left child 3, and right child 8, what does postorder traversal return?
- A[3, 8, 5]
- B[5, 3, 8]
- C[3, 5, 8]
Show the answer
[3, 8, 5]. Left subtree (3), then right subtree (8), then the root (5) last.
Postorder traversal
Given the root of a binary tree, return the values of its nodes visited in postorder: every node in its left subtree, then every node in its right subtree, then the current node. If the tree is empty, return an empty list.
root = [5, 3, 8] → [3, 8, 5]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000