How Pre-Order Traversal Works
Pre-order traversal visits a node before its subtrees. That order is what you need to copy a tree or serialise it, because a parent always arrives before the children that hang off it.
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
Pre-order walk over 7 values, 3 levels deep.
Counters
- Visited
- 0/7
- On the stack
- 0
- Tree height
- 3
- Nodes
- 7
Settings
More options
Pre-order
- 1
stack = [root] - 2
while stack: - 3
node = stack.pop() - 4
visit(node) - 5
push node.right - 6
push node.left
What each walk is for
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-order | Values in sorted order | O(n) | O(h) |
| Pre-order | Root before children, for copying a tree | O(n) | O(h) |
| Post-order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
Scroll the table sideways for the rest of the columns.
n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n, which is what balancing prevents.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(h) |
How pre-order traversal works
Pre-order traversal emits the current node, then walks the left subtree, then the right. Because every parent is emitted before its descendants, the resulting sequence can be replayed to rebuild the tree with the same structure. Insert them in that order and you get the original shape back. In-order cannot do that: its output is sorted, and sorted input builds a completely different tree.
- If the node is empty, return.
- Visit the node: emit it now, before looking at any child.
- Traverse the left subtree in full.
- Traverse the right subtree in full.