Tree DFS¶
Also known as: Depth-First Search on Trees, Preorder / Inorder / Postorder Traversal, Recursive Tree Walk
Go as deep as you can down one branch, then come back up and take the next. The recursion handles the bookkeeping. The only real decision is when you do the work: before the children (preorder), between them (inorder), or after both have reported back (postorder) — and that choice is what makes a problem easy or impossible.
Before you start¶
What 'solved properly' looks like
Target: O(n) time, O(h) space where h is the tree's height. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You visit a node, then recursively visit all its children (or its left and right subtrees). The three traversal orders change only what you do at the node itself: process it before the children (preorder), after the left but before the right (inorder), or after both children (postorder). Most tree problems are postorder — you need both subtrees' answers before you can compute the parent's answer.
Why it matters: Most tree questions are "compute something for each subtree and combine" — which is postorder DFS. Once you see that, half the tree canon collapses into one shape. And the recursive thinking you practise here is exactly what graph DFS and backtracking will demand later.
When to reach for it¶
Reach for it for root-to-leaf paths, computing depth or height, checking whether a path sums to something, validating a BST, comparing two trees or subtrees, or anything where the answer for a node depends on the answers from its children.
When not to use it
If you need the shallowest answer or a level-by-level view, BFS is the right tool and DFS will make you work for it. On a skewed tree (a linked list in disguise) the recursion is n frames deep — that's a real stack-overflow risk on large inputs, not a theoretical one.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Maximum Depth of Binary Tree | LeetCode | Easy | 10 mins | teaching |
| 2 | Invert Binary Tree | LeetCode | Easy | 15 mins | teaching |
| 3 | Same Tree | LeetCode | Easy | 15 mins | consolidation |
| 4 | Path Sum | LeetCode | Easy | 20 mins | consolidation |
| 5 | Validate Binary Search Tree | LeetCode | Medium | 25 mins | challenge |
Already know this? Test out.
If you can solve Validate Binary Search Tree cleanly in one sitting — handling the min/max bounds correctly rather than just checking parent vs child — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.