Three orders that differ by one line#
Every depth-first traversal of a binary tree does the same three things: visit the node, walk the left subtree, walk the right subtree. All that changes is where the visit sits.
preorder: visit, left, right
inorder: left, visit, right
postorder: left, right, visit
That is not a mnemonic to memorise. It is a choice about when you look at a node: on the way down, in between, or on the way back up. And that choice is what each order is for.
| Order | Look at a node | Use it when |
|---|---|---|
| Preorder | before its children | copying a tree, writing one out, anything where the parent must exist first |
| Inorder | between its subtrees | a search tree, where this produces sorted order |
| Postorder | after both children | you need answers from below first: heights, sizes, deleting |
Postorder is the one to notice. Almost every tree problem that computes something, the depth, the diameter, whether it is balanced, is postorder: you cannot answer for a node until both children have answered.
Level order is different in kind#
The other three are recursive, and recursion goes deep first: it follows one child all the way down before touching the other. Level order needs the opposite, so it cannot be written the same way.
Use a queue. Take a node off the front, record it, put its children on the back. Children always go behind everything already waiting, so nothing at depth 2 can come out before something at depth 1.
Swap that queue for a stack and you get preorder again. The container is the traversal.
Levels, not just nodes#
Plenty of questions are about a level rather than a node: the right view, the deepest level's sum, the zigzag order. The trick for all of them is the same:
while the queue is not empty:
n = size of the queue # exactly one level
for i in 1..n:
...
Reading the size before draining works because anything you add during the pass belongs to the next level. It is two extra lines and it turns level order into level-by-level.
Where this is going#
Level order on a tree, plus a "have I been here before" check, is breadth-first search on a graph. Preorder, plus the same check, is depth-first search. Trees are the easy case because there is exactly one way to reach each node, so nothing has to be remembered. When you meet graphs, you are meeting these traversals again with one extra guard.
Practice in order#
- Level order, for the queue.
- The right view, for counting a level before draining it.
- Maximum depth, the shortest postorder there is.
- Same tree and invert a binary tree, both preorder, both four lines.