Visiting every node in a tree, and the fact that the order is a choice.
A tree holds its data in a shape, not in a sequence. So the moment you want to do something to every node — print them, sum them, free them, write them to a file — you have to pick an order to meet them in. There are four standard answers, they all cost , and they are not interchangeable. Choosing the wrong one gives you code that nearly works, which is the most expensive kind.
The lessons
- Depth-First Traversals — [Intermediate] — pre-order, in-order and post-order: the three orders that go deep before going wide. Each one recursively and iteratively with an explicit stack, including the two standard tricks for iterative post-order
- Level-Order Traversal — [Intermediate] — the one that is not depth-first: a queue instead of a stack, and the level-by-level sweep that falls out of it
The thread through both
The three depth-first orders are the same algorithm with the visit moved. Pre-order visits the node before its subtrees, in-order between them, post-order after. That is the entire difference, and everything else — which problems each one solves, which is awkward to write iteratively — follows from it.
How you choose between them is not a matter of taste. It is decided by which way the information flows:
- If a node’s answer depends on what is above it — its depth, the path taken to reach it — you need the answer before you descend, so go top-down with pre-order.
- If a node’s answer depends on what is below it — its height, the size of its subtree, whether it is balanced — you need the children’s answers first, so go bottom-up with post-order.
- If you want the values of a binary search tree in sorted order, that is in-order, and it is the property the whole structure exists to provide.
- If you care about distance from the root — the shallowest node matching something, or a level-by-level view — you need level-order, and a queue.
Recursion is a stack you did not have to write. Both lessons make that concrete: the iterative versions do exactly the same work as the recursive ones, with the bookkeeping moved from the call stack into a list you control. It matters because the call stack is small and fixed, and a list is not — which is why a 3,000-node chain crashes one version and not the other.
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
Related
- Binary Trees — the structure being walked
- Binary Search Trees — where in-order earns its place
- Stacks and Queues — the stack and the queue these are built on
- Depth-First Search · Breadth-First Search — the same two ideas on a general graph, where cycles mean you also need a visited set
- the trees folder
Software engineering
Infrastructure & security
Computer science
Hardware & engineering