Chapter 23: DSA Pre-order Traversal
DSA Pre-order Traversal – Let’s learn this topic properly, like I’m sitting next to you with a whiteboard, drawing the tree, walking through every step slowly, showing exactly what happens at each moment, and explaining why pre-order is useful and when you should choose it.
What is Pre-order Traversal?
Pre-order traversal is one of the three classic depth-first traversals of a binary tree.
The name pre-order tells you the rule very clearly:
Pre means before → We visit (process/print) the root node before visiting its subtrees.
So the visiting order is:
Root → Left subtree → Right subtree
This is the exact sequence you follow:
- Visit the current node (process it — print, store, compare, etc.)
- Recursively traverse the left subtree
- Recursively traverse the right subtree
Visual Rule – Very easy way to remember
Imagine you are walking around the tree:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
Visit here first (1) ↓ ┌───────┐ │ │ ┌────┴────┐ │ │ │ │ Visit left Visit right |
Pre-order = “Root first, then children”
Classic Example Tree (we’ll use this for everything)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 |
Pre-order traversal of this tree should give:
1 2 4 7 5 8 3 6 9
Let’s see exactly why:
Step-by-step walkthrough (very detailed)
Start at root = 1
- Visit 1 → print 1 (first thing we do is visit current node)
- Go to left child → node 2
- Visit 2 → print 2
- Go to left child of 2 → node 4
- Visit 4 → print 4
- Go to left child of 4 → node 7
- Visit 7 → print 7
- 7 has no children → backtrack
- 4’s right child = none → backtrack
- 2’s right child → node 5
- Visit 5 → print 5
- 5’s left = none
- 5’s right → node 8
- Visit 8 → print 8
- 8 has no children → backtrack
- backtrack from 5 → backtrack from 2
- Now go to right child of root → node 3
- Visit 3 → print 3
- 3’s left = none
- 3’s right → node 6
- Visit 6 → print 6
- 6’s left → node 9
- Visit 9 → print 9
- 9 has no children → backtrack
- 6’s right = none → backtrack
Final output: 1 2 4 7 5 8 3 6 9
Pre-order Traversal Code (most common interview versions)
1. Recursive (easiest to understand & most frequently written)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def preorderTraversal(root): result = [] def helper(node): if not node: return # Step 1: Visit root first result.append(node.val) # Step 2: Left subtree helper(node.left) # Step 3: Right subtree helper(node.right) helper(root) return result |
2. Iterative version using Stack (very common in interviews)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def preorderTraversal(root): if not root: return [] result = [] stack = [root] while stack: node = stack.pop() # take from top result.append(node.val) # visit immediately # Push right first (because stack is LIFO → right will be processed after left) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result |
Important note about iterative pre-order:
We push right child first, then left child → because stack is LIFO → left will be popped first → processed first
When is Pre-order Traversal used? (real applications)
| Use case | Why pre-order is perfect |
|---|---|
| Copying / cloning a tree | Root must be created before children |
| Serialize tree (prefix notation) | Root first makes reconstruction easier |
| Build expression trees (prefix) | Operator comes before operands |
| Create a mirror tree | Process root before subtrees |
| Topological sort in some tree-like DAGs | Parent before children |
| Some tree construction algorithms | Root-first order needed |
Pre-order vs In-order vs Post-order – Quick Comparison
| Traversal | Root visit position | Typical sorted order? | Most famous use case |
|---|---|---|---|
| Pre-order | First | No | Copy tree, prefix expr |
| In-order | Middle | Yes (in BST) | Sorted order, BST validation |
| Post-order | Last | No | Delete tree, postfix expr |
Summary – Pre-order Traversal in one line each
- Visit order: Root → Left → Right
- Root is processed before its subtrees
- Recursive: very natural and clean
- Iterative: use stack + push right before left
- Time complexity: O(n) (visit each node once)
- Space complexity: O(h) recursive / O(n) worst iterative (skewed tree)
- Very common in interviews (traversal questions appear almost everywhere)
- One of the first traversal patterns you should master completely
Would you like to continue with the next traversal or any specific pre-order related topic?
Very natural next steps:
- In-order Traversal (recursive + iterative + BST magic)
- Post-order Traversal
- All three traversals comparison with same tree
- Iterative pre-order dry run step-by-step
- Pre-order traversal applications (expression tree, copy tree, etc.)
- Morris Traversal (O(1) space pre-order – advanced)
Just tell me which direction you want to go next — I’ll explain it with the same level of detail, visuals, and step-by-step clarity! 😊
