On this page
Description
Depth-first traversal visits a node and both its subtrees. The three classic orders differ only in when the node itself is handled: before its subtrees (preorder), between them (inorder) or after them (postorder). Each order fits a job. Preorder copies or serializes a tree, inorder reads a BST in sorted order, and postorder deletes or evaluates it. Add a path that grows on the way down and shrinks on the way back, and the same walk finds the route from the root to any node.
We'll go from simple to more technical:
- The pattern: preorder, inorder and postorder as one recursion.
- A second flavor: the root-to-node path, with backtracking.
- Which order fits which production job.
- The bugs: wrong order, missing backtrack, and comparing two trees safely.
The approach: the three traversal orders
At every node there are three things to do: handle the node, walk its left subtree and walk its right subtree. The subtrees always go left before right. The only choice is where the node goes in that sequence.
| Order | When the node is handled | Visits |
|---|---|---|
| Preorder | before its subtrees | 4 2 1 3 7 |
| Inorder | between its subtrees | 1 2 3 4 7 |
| Postorder | after its subtrees | 1 3 2 7 4 |
This tree is a BST, so inorder gives its values in sorted order.
Java
void inorder(TreeNode n) { if (n==null) return; inorder(n.left); visit(n); inorder(n.right); }
void preorder(TreeNode n) { if (n==null) return; visit(n); preorder(n.left); preorder(n.right); }
void postorder(TreeNode n) { if (n==null) return; postorder(n.left); postorder(n.right); visit(n); }
Python
def inorder(n: TreeNode | None) -> None:
if n is None:
return
inorder(n.left)
visit(n)
inorder(n.right)
def preorder(n: TreeNode | None) -> None:
if n is None:
return
visit(n)
preorder(n.left)
preorder(n.right)
def postorder(n: TreeNode | None) -> None:
if n is None:
return
postorder(n.left)
postorder(n.right)
visit(n)
A second flavor: the path from the root to a node
To find the route to a node, keep a list path. Add each node when you arrive. If neither subtree leads to the target, remove the node again before returning. Searching for 3 in the tree above: add 4, add 2, add 1. Node 1 is a dead end, so remove it. Then add 3: found, and path is [4, 2, 3].
Java
boolean find(TreeNode node, int target, List<Integer> path) {
if (node == null) return false;
path.add(node.val);
if (node.val == target) return true;
if (find(node.left, target, path) || find(node.right, target, path)) return true;
path.remove(path.size() - 1); // this branch didn't lead to the target - undo it
return false;
}
Python
def find(node: TreeNode | None, target: int, path: list[int]) -> bool:
if node is None:
return False
path.append(node.val)
if node.val == target:
return True
if find(node.left, target, path) or find(node.right, target, path):
return True
path.pop() # this branch didn't lead to the target - undo it
return False
Add on the way in, remove on a dead end. That keeps path equal to the route to wherever the search is right now. It's the same push-then-pop shape as backtracking in Backtracking: Subsets & Choices.
Where you'll see it
Sorted sets and maps built on search trees list their contents with an inorder walk. Deleting a tree safely is postorder: children before the parent. Saving a tree is often preorder, because the reader learns each node before the subtrees it has to build under it. Finding one file's full path in a folder tree is the root-to-node search.
Which tool for which job?
| You need | Use |
|---|---|
| Copy or serialize a tree | preorder (root first) |
| A BST's values in sorted order | inorder |
| Delete a tree, or evaluate an expression tree | postorder (children first) |
| The path from the root to a node | DFS with a path you push and pop |
| Compare two trees | recurse on both together, nulls first |
| No recursion | an explicit stack (postorder: reverse root-right-left) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Freeing a node before its children | children become unreachable | postorder for deletion |
| No pop after a failed branch | the path keeps dead-end nodes | remove the node before returning |
Reading .val before checking both nodes for null | NullPointerException | if p == null or q == null: return p == q |
| Copying the path at every node | O(n x h) copies | one list, push and pop |
Pushing null children onto a Java ArrayDeque | NullPointerException | push only non-null children |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why does deleting a tree need postorder rather than preorder?
Show answer
If you delete a node first, you lose your only way to reach its children. In a garbage-collected language they're orphaned; in manual memory management you read freed memory. Postorder handles both children first, so deleting the parent last never needs anything that's gone.
2. The search finds the target in the left subtree. Does find(node.left, ...) || find(node.right, ...) still search the right subtree?
Show answer
No. || stops as soon as the left call returns true. With a unique target, searching the right side anyway would only waste time. With a duplicate value, it would add a second route to the path, so stopping at the first match keeps the path meaningful.
3. A same-tree check compares p.val == q.val before checking either node for null. What breaks?
Show answer
When exactly one of them is null, reading .val from it crashes before the code can report "different". Handle the null cases first: both null means equal, and one null means different. Only then compare values.
Key takeaways
- Preorder, inorder and postorder differ only in when the node is handled: before, between or after its subtrees.
- Preorder copies and serializes, inorder sorts a BST, postorder deletes and evaluates.
- For a root-to-node path, add the node on the way in and remove it on a dead end.
||stops at the first match, which keeps the path to a single route.- When walking two trees at once, check for nulls before reading any value.