Chapter 4: Depth First Search & Trees
Master recursive thinking and tree data structures. Learn how DFS explores paths to their deepest point before backtracking, and apply this pattern to solve classic tree problems including path sums, balanced checks, BST validation, and lowest common ancestor.
Chapter Overview
Trees are one of the most important data structures in computer science. They model hierarchical relationships---file systems, organizational charts, HTML documents, and decision processes all have tree-like structure. The ability to traverse and manipulate trees is fundamental to almost every area of software engineering.
Depth First Search (DFS) is the natural way to explore a tree: go as deep as possible along one branch before backtracking and trying the next. DFS maps elegantly onto recursion, making recursive thinking the key skill for this chapter.
Before diving into trees, we review recursion itself---understanding base cases, recursive cases, and how the call stack works. Then we build up from basic traversals to increasingly sophisticated tree problems: computing depth, checking balance, inverting structure, validating BST properties, and finding common ancestors.
This chapter covers:
- Recursion fundamentals: Base cases, stack frames, and tree recursion
- Binary tree structure: Nodes, edges, height, depth, and traversal orders
- DFS patterns: Tracking state, returning values, and combining results from subtrees
- Classic tree problems: Maximum depth, balanced check, inversion, BST validation, and LCA
Chapter Roadmap
Click any topic to jump in
Recursion Basics
Base case and recursive case — the decomposition that makes every tree algorithm in this chapter possible.
Trees are the most natural recursive structure — the call stack follows the tree exactly.
Tree Fundamentals
Nodes, children, and the three canonical traversal orders — pre-order, in-order, and post-order.
DFS Template
Pass state down, return values up — the reusable skeleton that solves most recursive tree questions.
Maximum Depth
A one-line DFS that returns $1 + \max(\text{left}, \text{right})$ — the simplest bottom-up computation.
Balance Checking
Propagate height up the tree and short-circuit on imbalance — $O(n)$ versus a naive $O(n^2)$.
Tree Mutation
Swap children recursively — a drop-in example of pre- vs post-order modifications.
BSTs
The in-order-sorted invariant enables $O(h)$ search, insert, and delete — $O(\log n)$ when balanced.
Lowest Common Ancestor
The canonical tree algorithm — works on any binary tree and is $O(1)$-per-node on a BST.
Recursion is a function calling itself with a smaller version of the same problem. Every recursive function has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into smaller subproblems.
Understanding how the call stack works is essential. Each recursive call creates a new stack frame with its own local variables. When the base case is reached, the frames "unwind" and combine their results back up.
In this topic
Base Case and Recursive Case
Every recursive function must define at least one base case (the simplest input that can be answered directly) and a recursive case (where the function calls itself with a smaller input). Without a base case, recursion never terminates and causes a stack overflow. The recursive case must always make progress toward the base case.
A recursion terminates iff every input eventually reaches a base case along every call path. Formally, define a well-ordering on inputs such that each recursive call has — the well-foundedness guarantees finite descent. Without a base case, you get infinite recursion; without strict descent, you get infinite recursion in a different disguise (e.g., calling ).
Write a recursive function to compute the factorial of n (n!).
Stack Frames and Tree Recursion
Each recursive call creates a stack frame holding local variables and the return address. Tree recursion occurs when a function makes two or more recursive calls, creating a branching call tree. The Fibonacci sequence is a classic example: fib(n) = fib(n-1) + fib(n-2). This creates exponential calls without memoization, which is why understanding the call tree matters for performance.
Each call adds a frame of size . For a balanced binary tree of nodes, DFS has depth , so call-stack memory is . For a skewed tree (linked list shape), depth is — which is why DFS on adversarial inputs can exhaust Python's default recursion limit of .
Write the recursive Fibonacci function and trace its call tree for fib(5).