Depth first, breadth first
Imagine exploring a building with many floors of rooms, where each room has doors to two smaller rooms:
- Depth-first (DFS): walk through one door, then the next door in that room, and keep going until you hit a dead end. Then walk back and try the other door. You go deep first.
- Breadth-first (BFS): visit every room on the first floor, then every room on the second floor, and so on. You go wide first, one level at a time.
In code, DFS is usually a recursive function (or a stack), and BFS uses a queue. A binary tree is a tree where each node has at most two children, left and right.
DFS visits a subtree completely before its siblings (pre-, in- or post-order depending on when the node itself is processed) and uses O(h) space for the recursion or stack, where h is the height; BFS visits by level using a queue and O(w) space, where w is the maximum width. Most tree problems are DFS with the right return value (what each subtree reports to its parent) or the right parameters (what each node receives from above, like bounds); BFS wins for anything per-level or shortest-path-shaped.
Senior concerns are the recursion depth on skewed trees, choosing traversal order deliberately (in-order on BSTs yields sorted output), and problems where information flows both down and up, like Lowest Common Ancestor. All in the Detailed version.
final class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(_ value: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
self.value = value; self.left = left; self.right = right
}
}
// DFS: recursion goes deep first
func sum(_ node: TreeNode?) -> Int {
guard let node else { return 0 }
return node.value + sum(node.left) + sum(node.right)
}
// BFS: a queue visits level by level
func values(byLevel root: TreeNode?) -> [Int] {
guard let root else { return [] }
var queue = [root], head = 0, result: [Int] = []
while head < queue.count {
let node = queue[head]; head += 1 // dequeue without O(n) removeFirst
result.append(node.value)
if let left = node.left { queue.append(left) }
if let right = node.right { queue.append(right) }
}
return result
}class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)
// DFS: recursion goes deep first
fun sum(node: TreeNode?): Int =
if (node == null) 0 else node.value + sum(node.left) + sum(node.right)
// BFS: a queue visits level by level
fun valuesByLevel(root: TreeNode?): List<Int> {
if (root == null) return emptyList()
val queue = ArrayDeque(listOf(root))
val result = mutableListOf<Int>()
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
result += node.value
node.left?.let(queue::addLast)
node.right?.let(queue::addLast)
}
return result
}class TreeNode {
int value;
TreeNode left, right;
TreeNode(int value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; }
TreeNode(int value) { this(value, null, null); }
}
// DFS: recursion goes deep first
static int sum(TreeNode node) {
if (node == null) return 0;
return node.value + sum(node.left) + sum(node.right);
}
// BFS: a queue visits level by level
static List<Integer> valuesByLevel(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>(List.of(root));
while (!queue.isEmpty()) {
TreeNode node = queue.pollFirst();
result.add(node.value);
if (node.left != null) queue.addLast(node.left);
if (node.right != null) queue.addLast(node.right);
}
return result;
}class TreeNode {
constructor(
public value: number,
public left: TreeNode | null = null,
public right: TreeNode | null = null,
) {}
}
// DFS: recursion goes deep first
function sum(node: TreeNode | null): number {
if (node === null) return 0;
return node.value + sum(node.left) + sum(node.right);
}
// BFS: a queue visits level by level
function valuesByLevel(root: TreeNode | null): number[] {
if (root === null) return [];
const queue = [root];
const result: number[] = [];
for (let head = 0; head < queue.length; head++) { // a read index instead of shift()
const node = queue[head];
result.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return result;
}Notice the shape of the recursive DFS: handle the empty tree (the base case), then combine the answers from both children with the current node. Almost every recursive tree function looks like that. The trick is trusting the recursion: assume sum(node.left) returns the right answer for the left subtree, and only think about what to do with it.
Maximum Depth of Binary Tree
Return the maximum depth of a binary tree: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.
3
/ \
9 20
/ \
15 7 → 3›
If you knew the depth of the left subtree and of the right subtree, what would the depth of the whole tree be?
›
Depth = 1 + the larger of the two subtree depths, and an empty tree has depth 0. That’s the whole recursion.
SolutionTry it yourself firstTime O(n)Space O(h)
func maxDepth(_ root: TreeNode?) -> Int {
guard let root else { return 0 }
return 1 + max(maxDepth(root.left), maxDepth(root.right))
}fun maxDepth(root: TreeNode?): Int =
if (root == null) 0 else 1 + maxOf(maxDepth(root.left), maxDepth(root.right))int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Every node is visited once: O(n) time. The recursion is as deep as the tree is tall: O(h) space, which is O(log n) for a balanced tree and O(n) for a tree shaped like a line. BFS solves it too: count the levels.
Choosing DFS or BFS
| Use | Why |
|---|---|
| DFS returning values (heights, sums, “is balanced”, diameter) | each subtree’s answer combines into its parent’s |
| DFS with parameters (BST bounds, path sums, depth so far) | information flows down from the root |
| In-order DFS on a BST | sorted order: k-th smallest, validate, two-sum in a BST |
| BFS | anything per level, minimum depth (stop at the first leaf), shortest path in unweighted graphs |
Space differs in an important way: DFS uses O(h) and BFS uses O(w). A balanced tree with a million nodes has h ≈ 20 but a last level of half a million nodes (the puzzle below); a degenerate, list-shaped tree has w = 1 but h = n, which overflows a recursive DFS. Production code on untrusted trees (user-generated nesting, parsed documents) uses an explicit stack or depth limits.
How wide does BFS get?
Predict the output
A perfectly balanced binary tree has 1,048,575 nodes (20 full levels). What is the largest size the BFS queue reaches?
BFS holds one level at a time (plus part of the next), and the last level of a perfect tree with 20 levels has 2¹⁹ = 524,288 nodes, half of all nodes. A recursive DFS on the same tree is only 20 calls deep. For wide trees, DFS uses far less memory; for deep, narrow trees, BFS does. On mobile, a BFS over a huge tree can be a memory spike, not just a time cost.
| Pattern | Shape | Examples |
|---|---|---|
| DFS returning a value | f(node) = combine(node, f(left), f(right)) | max depth, balanced, diameter, path sum |
| DFS with parameters | pass bounds / path state down | validate BST, root-to-leaf paths |
| In-order on BST | left, node, right = sorted | k-th smallest, BST iterator |
| BFS by level | size = queue.count, process size nodes | level order, right side view, min depth |
| Bottom-up both ways | return found-info, decide at node | LCA, diameter, max path sum |
Space: DFS O(h) (O(log n) balanced, O(n) skewed), BFS O(w). Gotchas: BST checks against children only, Int.MIN/MAX as sentinels, recursion depth on skewed or user-generated trees, serialization without null markers, removeFirst() on Swift arrays (or shift() in TypeScript) as a queue.
func preorder(_ root: TreeNode?) -> [Int] {
var stack = [root].compactMap { $0 }, out: [Int] = []
while let node = stack.popLast() {
out.append(node.value)
if let r = node.right { stack.append(r) } // right first, so left is processed first
if let l = node.left { stack.append(l) }
}
return out
}fun preorder(root: TreeNode?): List<Int> {
val stack = ArrayDeque<TreeNode>().apply { root?.let { addLast(it) } }
val out = mutableListOf<Int>()
while (stack.isNotEmpty()) {
val node = stack.removeLast()
out += node.value
node.right?.let(stack::addLast) // right first, so left is processed first
node.left?.let(stack::addLast)
}
return out
}List<Integer> preorder(TreeNode root) {
List<Integer> out = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
out.add(node.value);
if (node.right != null) stack.push(node.right); // right first, so left is processed first
if (node.left != null) stack.push(node.left);
}
return out;
}function preorder(root: TreeNode | null): number[] {
const stack = root ? [root] : [];
const out: number[] = [];
while (stack.length > 0) {
const node = stack.pop()!;
out.push(node.value);
if (node.right) stack.push(node.right); // right first, so left is processed first
if (node.left) stack.push(node.left);
}
return out;
}Check this part
Which data structure does breadth-first search use?
What is the base case in most recursive tree functions?
DFS uses O(h) space and BFS O(w). Which is smaller for a balanced tree of a million nodes?
A recursive DFS runs on user-generated nesting shaped like a long chain. What is the risk, and the fix?