Visiting every node
A tree stores things in a branching shape: a folder with subfolders, a web page with elements inside elements, an expression with brackets. To do anything with all of it (print it, search it, add it up) you must visit every node exactly once. That is a traversal.
A list has one obvious order. A tree does not. At every node there is a choice of where to go next.
Depth-first: go to the bottom before going sideways
Depth-first traversal follows one branch all the way down, then backs up to the last place it had a choice and takes the other branch.
The whole method is one small recursive function:
def walk(node):
if node is None:
return
walk(node.left)
walk(node.right)"Walk a tree" means "walk its left part, then walk its right part". Each part is itself a tree, so the same function handles it. The same pattern repeats at every level, on a smaller piece each time.
Visited so far
Start. Visit the node, then its left side, then its right side. The same rule is applied again at every node.
- Depth right now
- 0
- Calls in progress
- –
Watch the "calls in progress" line. It is the path from the top of the tree to where the walk is now. Stepping down adds a call. Finishing a node removes one. This list is the call stack, and it is all the memory a depth-first walk needs: one entry per level, however many nodes there are.
Three orders
Nothing above says when to actually do something with a node. There are three places to put that line, and they give three different orders.
def walk(node):
if node is None:
return
# visit(node) here: pre-order
walk(node.left)
# visit(node) here: in-order
walk(node.right)
# visit(node) here: post-orderThe route through the tree is identical in all three. Only the moment of the visit changes.
Visited so far
Start. Visit the node, then its left side, then its right side. The same rule is applied again at every node.
- Depth right now
- 0
- Calls in progress
- –
| Order | Rule | Result on this tree | Good for |
|---|---|---|---|
| Pre-order | Node, left, right | D B A C F E G | Copying a tree, printing a folder before its contents |
| In-order | Left, node, right | A B C D E F G | Reading a search tree in sorted order |
| Post-order | Left, right, node | A C B E G F D | Deleting a tree, working out folder sizes: children first |
Example
Why post-order for folder sizes
The size of a folder is the sum of the sizes of everything inside it. You cannot know a folder's size until you know its subfolders' sizes. So each subfolder must be finished before its parent is visited. That is post-order.
The other way: breadth-first
Depth-first is not the only choice. Breadth-first traversal visits level by level: the root, then all its children, then all their children. It uses a queue of nodes to visit, where depth-first uses the call stack.
| Depth-first | Breadth-first | |
|---|---|---|
| Goes | Down a branch, then backs up | Across a level, then the next |
| Remembers | One path: as deep as the tree | One level: as wide as the tree |
| Finds first | Whatever is down the first branch | Whatever is closest to the root |
Use breadth-first when you want the nearest match. Use depth-first when you need to reach the leaves, or when children must be handled before or after their parent.
Key takeaways
- A traversal visits every node of a tree once.
- Depth-first goes down one branch fully before trying the next. It is naturally recursive.
- The call stack holds the path from the root to the current node.
- Pre-order, in-order and post-order follow the same route and differ only in when the node is visited.
- In-order reads a search tree in sorted order. Post-order handles children before their parent.