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.
- Topics
- 8
- Demos
- 8
- Min read
- 33
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.
Topics
8 topics in this chapter
A folder on your laptop contains files and more folders, which contain files and more folders, nested to an unknown depth, and you want the total size of everything inside. A loop does not fit naturally, because you do not know in advance how many levels to descend. What you do know is that a folder's size is the size of its files plus the sizes of its subfolders, and each subfolder is the same problem, only smaller.
The previous chapter, Two Pointers & Sliding Window, solved problems with a flat left-to-right sweep. Trees and nested data are not flat, and recursion is the tool that matches their shape: a function answers a small input directly and, for anything larger, calls itself on smaller pieces and combines the results. Each pending call waits on the call stack, so recursion also costs memory proportional to its depth.
We first pin down the two parts every recursive function needs, a base case and a recursive case that makes progress. Then we look at stack frames and tree recursion, where a function calls itself more than once and the number of calls can explode.
Definition
A recursive function solves a problem by calling itself on strictly smaller inputs. It needs a base case, answered directly without recursion, and a recursive case that reduces the input toward that base case and combines the results. Each active call occupies a stack frame, so the extra space used is proportional to the maximum recursion depth.
In this topic
- 1Base Case and Recursive Case
- 2Stack Frames and Tree Recursion
Base Case and Recursive Case
A recursive function is only correct if every chain of calls eventually stops, so it needs two parts. The base case is the smallest input, answered directly, such as factorial(1) = 1. The recursive case handles larger input by calling the function on a strictly smaller input and combining the result, such as n * factorial(n - 1). Correctness follows by induction: if the base case is right and each step is right given a correct smaller answer, every input is right. The classic failure is a base case the input can skip past, which recurses until the stack overflows.
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
Every call gets its own stack frame holding its arguments, local variables, and the place to return to, and the frame stays on the call stack until the call returns. The deepest chain of pending calls therefore sets the memory cost: recursion depth d means O(d) space. When a function calls itself more than once, the calls form a call tree. Fibonacci, fib(n) = fib(n-1) + fib(n-2), is the standard example, and it recomputes the same subproblems again and again, so its running time grows exponentially, roughly as 1.6^n. Caching results, called memoization, collapses the tree to n distinct calls.
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).
Related Problems on PixelBank
A company org chart, a file system, and the HTML of a web page all share one shape: a single item at the top, and each item pointing to a few items below it, with no loops. Storing such data in a flat list loses the parent and child relationships that make it useful, and questions like "who reports to this manager, directly or indirectly?" become awkward to answer.
The previous topic, Recursion Review, showed that a problem can be solved by solving smaller copies of itself. A tree is the data structure with that property built in: every node's children are themselves the roots of smaller trees, called subtrees. A binary tree limits each node to at most two children, left and right, which keeps the code simple and underlies binary search trees, heaps, and expression trees.
We first fix the vocabulary, root, leaf, internal node, edge, depth, and height, and build a tree from node objects. Then we cover the three depth-first traversal orders, preorder, inorder, and postorder, which differ only in when a node is visited relative to its subtrees, and see what each order is good for.
Definition
A binary tree is either empty or a node holding a value plus two binary trees, its left and right subtrees. The root has no parent, leaves have no children, and every other node has exactly one parent. A node's depth is its number of edges from the root, and the tree's height is the greatest depth of any node.
In this topic
- 1Binary Tree Structure
- 2Tree Traversal Orders
Binary Tree Structure
A binary tree node stores a value and pointers to its left and right children. The tree is built recursively: each child is itself the root of a subtree. Key terminology includes root (topmost node), leaf (node with no children), internal node (node with at least one child), edge (connection between parent and child), height (longest path from root to leaf), and depth (distance from root to a specific node).
A binary tree with nodes has exactly edges (every non-root has one parent edge). If height is , then : the lower bound is a skewed tree (linked list), the upper bound is a perfect binary tree. This gives , so no algorithm can visit a tree in fewer than levels.
Define a binary tree node class and build a tree with values [1, 2, 3, 4, 5].
Tree Traversal Orders
A depth-first traversal visits every node once, and the three standard orders differ only in when the current node is handled relative to its two subtrees. Preorder visits the node, then left, then right; because parents come first, it suits copying or serializing a tree. Inorder visits left, node, right; on a binary search tree it yields the values in sorted order. Postorder visits left, right, node; because children come first, it suits freeing memory or computing sizes and heights. Each order is a three-line recursive function running in O(n) time and O(h) stack space, where h is the height.
Pre-order, in-order, and post-order all visit every node exactly once, so each is time and call-stack space. They differ in when the current node is processed relative to its children. In-order on a BST yields a sorted sequence — that property uniquely determines BSTs among binary trees given a matching pre-order.
Implement all three DFS traversal orders and show their output for the tree [1, 2, 3, 4, 5].
Given a family tree, you might need to know whether any line of descent adds up to a particular inheritance, how many people are in each branch, or which branch is the deepest. Each question sounds different, and writing a new traversal from scratch for every one quickly becomes error-prone.
The previous topic, Tree Fundamentals, introduced the three traversal orders as ways to list nodes. Depth-first search (DFS) on trees uses the same recursive walk to compute answers rather than lists. Almost every tree problem reduces to two decisions: what information to pass down to the children through parameters, such as a running sum, the current depth, or allowed bounds, and what to return up to the parent, such as a count, a height, or a yes/no verdict. Once those two choices are made, the code nearly writes itself, and it visits each node once in O(n) time.
We first practice the down-and-up flow on the path-sum problem, where the remaining target travels down and a verdict travels back up. Then we distill a reusable DFS template and see how preorder and postorder placement of the work changes what the function can compute.
Definition
Depth-first search on a tree visits a node and then fully explores one subtree before starting the next. Implemented recursively, it can pass state down through parameters and return results up through return values, visiting every node once. It runs in O(n) time and uses O(h) stack space, where h is the tree's height.
In this topic
- 1Passing State Down and Returning Values Up
- 2DFS Template for Trees
Passing State Down and Returning Values Up
A recursive call sees only its own node, so context from above arrives as a parameter and results leave as a return value. Passing down suits information that depends on the path from the root, such as a running sum, the current depth, or the ancestors' bounds. Returning up suits information that depends on the subtree below, such as its height, size, or validity. In path sum, the remaining target shrinks on the way down and each leaf reports whether it matches. A common bug is checking at a null child instead of at a leaf, which accepts paths that stop at internal nodes.
The DFS template is a fold: where combines the current node with its children's results. Total work is . For constant , this is linear — the same shape whether you are counting nodes, computing heights, or checking any local invariant.
Given a binary tree and a target sum, determine if there is a root-to-leaf path where the values sum to the target.
DFS Template for Trees
Most tree DFS functions share one skeleton. First, handle the empty tree, returning the neutral value for the question, such as 0 for counts or True for validity checks. Second, optionally do preorder work on the current node, using what was passed down. Third, recurse into the left and right subtrees. Fourth, do postorder work, combining the children's return values into this node's answer. Deciding where the work goes is most of the design: counting nodes needs only the combine step, 1 + left + right, while path problems do their work on the way down. The usual bug is an empty-tree value that breaks the combine step.
The template encodes two orthogonal axes: top-down state (passed as arguments) and bottom-up values (returned). Any tree problem fits somewhere in this 2D grid. Examples: 'path sum' uses top-down state; 'max depth' uses bottom-up values; 'diameter' uses both simultaneously. Time stays because each node is visited exactly once.
Count the total number of nodes in a binary tree using DFS.
Related Problems on PixelBank
A deeply nested JSON document crashes a parser that recurses once per level, and before accepting input you want to know how deep it goes. The same question appears whenever you size a recursion stack, estimate how long a tree lookup takes, or check whether a tree has degenerated into something close to a linked list.
The previous topic, DFS on Trees, introduced the down-and-up template. Maximum depth is its purest postorder instance: nothing needs to be passed down, and each node returns one number up. The depth of a tree is one more than the depth of its deeper subtree, and an empty tree has depth zero. Those two sentences are the whole algorithm, and they visit each node exactly once for O(n) time with O(h) stack space.
We first write and trace the recursive depth computation. Then we untangle the terminology, depth versus height and counting nodes versus counting edges, which differs between textbooks and LeetCode and causes many off-by-one errors in interview answers.
Definition
The maximum depth of a binary tree is the number of nodes on the longest path from the root down to a leaf, with the empty tree defined to have depth 0. Recursively, maxDepth(node) equals 1 plus the larger of maxDepth(node.left) and maxDepth(node.right). Computing it visits every node once, in O(n) time.
In this topic
- 1Recursive Depth Computation
- 2Depth vs Height Terminology
Recursive Depth Computation
The maximum depth of a binary tree follows a clean recursive definition: if the tree is empty, the depth is 0. Otherwise, it is 1 (for the current node) plus the maximum of the left subtree's depth and the right subtree's depth. This is a postorder pattern because we need the results from both children before computing the current node's answer. Time complexity is O(n) since we visit every node exactly once.
, with . The recurrence has total work regardless of shape — every node does combine work and is touched exactly once.
Find the maximum depth of a binary tree.
Depth vs Height Terminology
Depth of a node is its distance from the root (root has depth 0). Height of a node is its distance from the farthest leaf below it (leaves have height 0). The height of the tree equals the depth of its deepest leaf. Many problems use these interchangeably but understanding the distinction helps: depth is measured top-down, height is measured bottom-up. The max_depth function computes the height of the tree, which equals the maximum depth of any node.
Depth of a node is distance from the root; height of a node is distance to the deepest descendant. For the root of a tree with nodes: , . Tree height satisfies , giving . Balanced trees are the ones that live near the lower bound.
For each node in a tree, compute both its depth and its height.
Related Problems on PixelBank
A binary search tree built from already-sorted data turns into a long chain, and lookups that should take 20 steps suddenly take a million. Databases and language runtimes guard against this by keeping trees balanced, and before you can maintain balance, you need to be able to check it.
The previous topic, Maximum Depth, computed a single height with one postorder pass. A tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one. The obvious check calls the height function separately at every node, recomputing the same subtree heights repeatedly. The better check notices that the height pass already visits every subtree, so it can verify balance on the way back up and report failure with a sentinel value, all in a single O(n) pass.
We first build that bottom-up checker, which returns either a height or -1 for unbalanced and stops early once an imbalance is found. Then we compare it with the naive top-down version and count how much repeated work the naive version does, a pattern of merging computation with validation that recurs throughout tree problems.
Definition
A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most 1. A balanced tree with n nodes has height O(log n). Balance can be checked in O(n) time with one postorder pass that returns each subtree's height, or a sentinel such as -1 once any node violates the condition.
In this topic
- 1Bottom-Up Balance Checking
- 2Naive vs Optimal Approach
Bottom-Up Balance Checking
Checking balance needs every subtree's height, and computing those heights already visits every node, so the two jobs can share one postorder pass. Define check(node) to return the subtree's height when it is balanced and -1 when it is not. An empty tree returns 0. Otherwise, compute the left result and return -1 immediately if it is -1; do the same for the right. Then return -1 if the two heights differ by more than 1, or 1 + max(left, right) otherwise. The -1 sentinel cannot be a real height, so it carries failure upward and stops further work. The whole check is O(n) time and O(h) stack space.
The naive approach recomputes height at each node, giving (or on a skewed tree). The bottom-up fix: return height if balanced, (a sentinel) if not — each node is visited once for total. The short-circuit works because once any subtree is unbalanced, the whole tree is unbalanced and we can stop.
Check if a binary tree is height-balanced.
Naive vs Optimal Approach
The naive check works top-down: at each node it calls a separate height function on both subtrees, compares the results, and then recurses into the children to repeat the process. Every node's height is therefore recomputed once for each of its ancestors that gets checked. On a balanced tree that is O(n log n), and O(n^2) is a safe upper bound. The optimal check works bottom-up: one postorder pass returns heights and checks balance together, visiting each node once for O(n). The naive version is correct, just wasteful. Fusing a computation with its validation is a recurring tree pattern.
Both approaches check balance, but the naive version has a recurrence because height is recomputed, giving worst case. The optimal version has , which solves to . The principle generalises: whenever a recursive call would recompute information its parent already has, thread that information through the return value.
Compare the number of node visits for naive vs optimal balance checking on a skewed tree of height h.
Related Problems on PixelBank
A drawing app lets users flip a diagram of nested shapes horizontally, and the diagram is stored as a tree: every left child must become a right child, all the way down. Flipping only the root's two children would leave every deeper level still facing the original direction, so the change has to reach each node of the tree.
The previous topic, Balanced Binary Tree, read a tree and returned a verdict. Inverting a tree modifies it, which introduces a new concern: when a function changes a node, does it matter whether that change happens before or after the recursive calls on its children? For inversion, swapping a node's two child pointers and then inverting each subtree produces the mirror image in O(n) time and O(h) stack space, and the code fits in five lines.
We first write the swap-and-recurse version and trace it on a small tree, checking the result with an inorder traversal, which reverses under mirroring. Then we compare preorder and postorder placement of the swap, which both work here, with an inorder placement that quietly breaks. That case shows why the timing of a modification matters.
Definition
Inverting a binary tree produces its mirror image: at every node, the left and right subtrees are exchanged. Recursively, invert(node) swaps node.left and node.right and inverts both subtrees, returning the empty tree unchanged. It visits every node once, in O(n) time and O(h) stack space, and reverses the tree's inorder sequence.
In this topic
- 1Recursive Tree Modification
- 2Pre-order vs Post-order Modification
Recursive Tree Modification
To invert a binary tree, swap the left and right children of every node. Recursion makes this elegant: invert the left subtree, invert the right subtree, then swap them. The base case is a null node (nothing to invert). The order of operations does not matter here---you can swap first then recurse, or recurse first then swap---both produce the correct result. Time complexity: O(n), space: O(h) for the recursion stack.
Inverting a tree is the fold . Time is , space is stack. The operation is its own inverse: , which is a nice correctness check during debugging.
Invert a binary tree so that every left child becomes the right child and vice versa.
Pre-order vs Post-order Modification
When modifying tree structure, the order of operations matters. For inversion, both preorder (swap then recurse) and postorder (recurse then swap) work correctly. However, for other tree modifications, order matters. In preorder modification, you change the node before visiting children---useful when the modification affects which children to visit. In postorder modification, you process children first and then modify the parent based on children's final state---useful when the parent depends on the children's results.
For idempotent transforms like invert, pre- and post-order produce the same result — the final tree depends only on the set of swaps performed, not their order. But when a modification depends on children's results (e.g., 'attach a sum of descendants'), post-order is the only correct choice. Rule of thumb: if the computation at a node needs its children's final state, go bottom-up.
Show that preorder and postorder inversion produce the same result.
Related Problems on PixelBank
A phone's contact list must support fast lookup, and also fast insertion and deletion as contacts come and go. A sorted array gives O(log n) lookup through binary search, but inserting a new name means shifting everything after it, O(n) per insert. A hash map gives fast lookup and insertion but loses the ordering needed for "all names between Kim and Lee".
The previous topic, Invert Binary Tree, modified a tree's shape. A binary search tree (BST) gives the shape a meaning: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. That ordering turns each node into a binary-search decision, go left or go right, so search, insert, and delete all take O(h) time, where h is the height, and an inorder traversal reads the keys in sorted order.
We first implement search and insertion and see how insertion order determines the height. Then we tackle validation, deciding whether an arbitrary tree is a BST, where the tempting check of comparing each node only with its children is wrong, and the correct fix passes an allowed range down the recursion.
Definition
A binary search tree is a binary tree in which, for every node with key v, all keys in its left subtree are less than v and all keys in its right subtree are greater than v. Search, insertion, and deletion follow a single root-to-leaf path in O(h) time, and an inorder traversal lists the keys in sorted order.
In this topic
- 1BST Property and Search
- 2Validating BST with Range Checking
BST Property and Search
The BST property states that for every node with value v: all nodes in the left subtree have values < v, and all nodes in the right subtree have values > v. This enables binary search: at each node, compare the target with the node's value to decide whether to go left or right. Search time is O(h) where h is the tree height---O(log n) for balanced trees, O(n) for skewed trees.
A BST satisfies: for every node , all keys in 's left subtree are and all keys in the right are . Search follows the ordering: at each step you go left or right. Cost is ; for a balanced BST, , but an adversary can build a BST of height — which is why self-balancing variants (AVL, Red-Black, Treap) exist.
Implement search and insertion in a BST.
Validating BST with Range Checking
A common mistake is checking only that node.left.val < node.val < node.right.val. This fails when a deeper node violates the BST property with an ancestor. The correct approach passes a valid range (min, max) down the recursion. The root can be anything (range: -inf to +inf). When going left, the max becomes the parent's value. When going right, the min becomes the parent's value. Every node must fall within its inherited range.
Check the invariant that every node's key lies in an allowed range . Initially the range is ; recursing left tightens to the current key, recursing right tightens . The alternative — checking only parent/child pairs — is wrong because a distant ancestor can impose a binding constraint. Total time , space .
Determine if a binary tree is a valid BST.
Two git branches diverged weeks ago, and to merge them git needs the most recent commit they share, called the merge base. A family tree asks the same of two cousins, and a file system of two files. Each is the same question: where do the paths from the root to two nodes last overlap?
The previous topic, BST Introduction & Valid BST, used the ordering of keys to steer a search down one path. The lowest common ancestor (LCA) of nodes p and q is the deepest node that has both in its subtree, where a node counts as its own ancestor. Storing both root-to-node paths and comparing them works, but a single DFS can do better: each call reports whether it found p or q below it, and the first node to hear "found" from both sides is the answer, in O(n) time.
We first build that recursive LCA for a general binary tree and trace both the split case and the case where one node is the other's ancestor. Then we exploit the BST ordering to find the LCA along a single root-to-leaf path in O(h) time.
Definition
The lowest common ancestor of nodes p and q in a rooted tree is the deepest node that has both p and q as descendants, where every node counts as a descendant of itself. In a binary tree it is found with one DFS in O(n) time; in a binary search tree, the ordering of keys finds it in O(h) time.
In this topic
- 1Recursive LCA Algorithm
- 2LCA in a Binary Search Tree
Recursive LCA Algorithm
The recursive approach works as follows: if the current node is null, return null. If the current node is p or q, return it (we found one of the targets). Recurse on both children. If both children return non-null, the current node is the LCA (p and q are in different subtrees). If only one child returns non-null, propagate that result upward (both targets are in the same subtree). Time complexity: O(n), space: O(h) for recursion stack.
For any binary tree, satisfies: if both and are in the left subtree, recurse left; if both in the right, recurse right; otherwise is the LCA. Each node does combine work and is visited once, giving time and space. Correctness: the first node on the root-to-leaf path that has and on different sides is the deepest common ancestor.
Find the lowest common ancestor of nodes p and q in a binary tree.
LCA in a Binary Search Tree
In a BST, finding the LCA is simpler because the BST property tells us which subtree to search. If both p and q are smaller than the current node, the LCA is in the left subtree. If both are larger, it is in the right subtree. If they split (one smaller, one larger), the current node is the LCA. This runs in O(h) time---O(log n) for balanced BSTs. No need to search both subtrees.
The BST version exploits ordering: at each node , if go left; if both go right; otherwise is the LCA. This path length is — on a balanced BST — strictly better than the generic binary-tree algorithm because BST ordering lets you skip entire subtrees.
Find the LCA of two nodes in a BST more efficiently using the BST property.