A tree traversal method that visits nodes in the order: root, left child, right child. It's used to create a copy of the tree.
1 2 3 4 5 6 7 8 9 10 11 12
{
"status": "starting traversal"
}Overview
Pre-order traversal visits the current node first, then its left subtree, then its right subtree. Because each parent is visited before any of its descendants, the output describes the tree from the top down.
That top-down order is exactly what you need to copy or serialise a tree: if you write nodes in pre-order (including markers for null children), you can rebuild the identical tree by reading them back in the same order. File-system listings and expression trees printed in prefix (Polish) notation follow the same pattern.
On the default tree (root 10, children 5 and 15, leaves 2, 7, 12, 18), pre-order visits 10, 5, 2, 7, 15, 12, 18. Notice that the root always comes first and that the whole left branch is finished before 15 is visited.
Step by step
- If the current node is null, return.
- Visit the current node.
- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
Complexity
| Case | Cost | Why |
|---|---|---|
| Time | O(n) | Each node is visited once. |
| Space (balanced tree) | O(log n) | Recursion depth equals tree height. |
| Space (skewed tree) | O(n) | Height can be n. |
When to use it
- Cloning or serialising a tree so it can be rebuilt later.
- Printing hierarchical data such as folders or an organisation chart with indentation.
- Converting an expression tree to prefix notation.
Common mistakes
- In an iterative version with a stack, push the right child before the left so the left is processed first.
- Serialising without null markers loses information — different trees can produce the same sequence.
- Deep recursion on skewed trees can overflow the stack.
A dry run is the best way to check your understanding of Pre-order Traversal: follow each row, predict the next one, and compare. The run below takes 60 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- Binary tree (see the input box above)
- Result
- final_path = [10, 5, 2, 7, 15, 12, 18]
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = starting traversal |
| 3 | 5 | current_node = 10, action = visiting node |
| 5 | 8 | from_node = 10, action = traversing left |
| 7 | 5 | current_node = 5, action = visiting node |
| 9 | 8 | from_node = 5, action = traversing left |
| 11 | 5 | current_node = 2, action = visiting node |
| 13 | 8 | from_node = 2, action = traversing left |
| 15 | 3 | node = is null, action = return |
| 16 | 9 | from_node = 2, action = traversing right |
| 18 | 3 | node = is null, action = return |
| 19 | 11 | finished_subtree_at = 2, action = return |
| 20 | 9 | from_node = 5, action = traversing right |
| 22 | 5 | current_node = 7, action = visiting node |
| 24 | 8 | from_node = 7, action = traversing left |
| 26 | 3 | node = is null, action = return |
| 27 | 9 | from_node = 7, action = traversing right |
| 29 | 3 | node = is null, action = return |
| 30 | 11 | finished_subtree_at = 7, action = return |
| 31 | 11 | finished_subtree_at = 5, action = return |
| 32 | 9 | from_node = 10, action = traversing right |
| 34 | 5 | current_node = 15, action = visiting node |
| 36 | 8 | from_node = 15, action = traversing left |
| 38 | 5 | current_node = 12, action = visiting node |
| 40 | 8 | from_node = 12, action = traversing left |
| 42 | 3 | node = is null, action = return |
| 43 | 9 | from_node = 12, action = traversing right |
| 45 | 3 | node = is null, action = return |
| 46 | 11 | finished_subtree_at = 12, action = return |
| 47 | 9 | from_node = 15, action = traversing right |
| 49 | 5 | current_node = 18, action = visiting node |
| 51 | 8 | from_node = 18, action = traversing left |
| 53 | 3 | node = is null, action = return |
| 54 | 9 | from_node = 18, action = traversing right |
| 56 | 3 | node = is null, action = return |
| 57 | 11 | finished_subtree_at = 18, action = return |
| 58 | 11 | finished_subtree_at = 15, action = return |
| 59 | 11 | finished_subtree_at = 10, action = return |
| 60 | 14 | final_path = [10, 5, 2, 7, 15, 12, 18] |