Tree traversals
A tree has no single obvious order, so there are three standard ones. They all walk the same path, left side first. The only difference is when each node is written down: before its children (pre), between them (in) or after them (post).
visit orders, first visit at the top
pre-order
in-order
post-order
This tree came from inserting the values in order. Walk it and record each node at three moments: before, between and after its children.
1function walk(node, pre, inOrder, post) {2 if (node === null) return;3 pre.push(node.value);4 walk(node.left, pre, inOrder, post);5 inOrder.push(node.value);6 walk(node.right, pre, inOrder, post);7 post.push(node.value);8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every node is visited once |
| average | n | any shape of tree |
| worst | n | the same for every tree |
| space | h | one waiting call per level: n for a chain |
Where it breaks
- Picking the wrong order. In-order gives sorted output, but only for a binary search tree. Pre-order is the one to use when copying or saving a tree, since parents come before children. Post-order frees children before their parent.
- A chain is deep. Pick A chain: every node hangs off the one before, so the recursion goes n calls deep. A long enough chain overflows the stack, which is why big trees are often walked with an explicit stack instead.
- Pre-order alone is ambiguous. Several different trees share the same pre-order. To rebuild a tree exactly you need two of the orders, for example pre-order with in-order.