Tree Traversals

Four ways to visit every node of a binary tree, and why the order differs.

The idea (a company org chart)

A tree is like an org chart: one boss at the top, and each person has at most two direct reports (a left and a right child). “Traversal” means walking through everyone exactly once. The only question is when you say hello to a person:

The three recursive versions are the same function with the line visit moved. Watch the call stack grow when we go down and shrink when a call returns.

Watch it work

Try it

Common mistakes

Complexity, in plain English: every node is visited once, so the time grows in step with the number of nodes (O(n)). The recursive versions need space equal to the tree’s height; level-order needs space equal to the widest floor.