Introduction to DFS
Explore data structures deeply by following a path to its end before backtracking.
What is Depth-First Search?
Depth-First Search (DFS) is a fundamental graph and tree traversal algorithm.
Imagine you are in a maze. A DFS strategy is to pick a path and keep walking until you hit a dead end. Once you hit a wall, you backtrack (retracing your steps) to the last intersection and try a different path. You explore depth first, diving as deep as possible before checking neighbors.
The Motivation: Reaching the Furthest Leaf
Consider a problem where you need to reach a specific node that is known to be very deep in a massive tree, or you need to generate a path from the root to a leaf.
"Given a binary tree, find a path that sums to X."
If the tree has height 1000, the target might be 1000 steps away.
Attempt 1: Breadth-First Search (Why it might fail)
Your instinct might be to check the closest nodes first (Level 1, then Level 2...). This is BFS.
While BFS finds the shortest path, it has a major drawback: Memory Usage.
To check Level 10, you must store ALL nodes of Level 9 in memory. For a full binary tree, the number of nodes doubles at each level. At depth 20, you might need to store 1 million nodes in your Queue just to take one more step! This can lead to Memory Limit Exceeded.
Visualizing the Memory Issue
Picture the tree widening as it goes down. BFS has to hold an entire level in its queue before it can move on, and a level of a full binary tree is as wide as everything above it put together. DFS holds only the path from the root to where it is — one node per level — so its memory grows with the height of the tree, not its width.
When should I use DFS?
Pattern Recognition Triggers:
Use DFS immediately if you see:
- "Find ANY path": You don't need the shortest path, just a valid one.
- "Visit Every Node": DFS is often cleaner to write recursively than BFS.
- Cycle Detection: DFS handles "visited in current path" logic naturally.
- Backtracking: Problems that require making choices and undoing them (Sudoku, N-Queens).
The Intuition: Stack & Recursion
DFS logic utilizes a LIFO (Last-In, First-Out) structure.
- Visit a node.
- Push its children onto a stack (or call recursively).
- Pop the most recently added child and visit it.
This means we always process the newest discovery first, leading us deeper and deeper until we run out of children (base case), triggering a backtrack.
Interactive Walkthrough
NODE · LEFT · RIGHT
CALL dfs(root)
Stack depth
0
Visited
0
call stack
No calls in progress
result
Nothing appended yet
Call dfs on the root, 1
Next
dfs(1): the node is not empty
Tree
Legend & Complexity
The node whose call is running
A call in progress, waiting for its children
Visited: already appended
Time
O(n)
Space
O(h) call stack
Run preorder DFS on a tree. The call running is filled, the calls waiting underneath it are outlined, and each node shows the order it was appended in. Every call on an empty child is drawn too, as a faded ∅ — that call really happens, and it is where each branch turns back.
Dry Run Table
Tree: [1, 2, 3, 4] — 1 has children 2 and 3, and 2 has a left child 4.
| Step | Call running | Call stack | Action | result |
|---|---|---|---|---|
| 1 | dfs(1) | [1] |
Append 1, go left | [1] |
| 2 | dfs(2) | [1, 2] |
Append 2, go left | [1, 2] |
| 3 | dfs(4) | [1, 2, 4] |
Append 4; both children are empty, return | [1, 2, 4] |
| 4 | dfs(2) | [1, 2] |
Right child is empty: return | [1, 2, 4] |
| 5 | dfs(1) | [1] |
Left side done, go right | [1, 2, 4] |
| 6 | dfs(3) | [1, 3] |
Append 3; both children are empty, return | [1, 2, 4, 3] |
| 7 | - | [] |
dfs(1) finishes: return [1, 2, 4, 3] |
[1, 2, 4, 3] |
The Solution Template
LeetCode 144, Binary Tree Preorder Traversal, in every language: return at an empty node, append the node, then recurse left and then right.
Introduction to DFS Code
1var preorderTraversal = function(root) {2 const result = [];34 function dfs(node) {5 if (!node) return;6 result.push(node.val);7 dfs(node.left);8 dfs(node.right);9 }1011 dfs(root);12 return result;13};
Edge Cases & Common Mistakes
Edge Case Checklist:
- Null Node: always check
if (!node) returnfirst. - Cycles: In graphs, you MUST track
visitednodes or you will loop infinitely. (Trees don't have cycles). - Stack Overflow: Extremely deep trees can crash recursion. Use iterative stack for production systems dealing with deep data.
Common Mistakes:
- Forgetting Base Case: Infinite recursion.
- Wrong Traversal Order: Processing node after children (Post-order) vs before (Pre-order) matters for logic.
Summary
Recap:
- The Trick: Use the system stack (recursion) to go deep.
- Movement: Visit -> Recurse Left -> Recurse Right.
- Efficiency: Low memory usage for balanced trees compared to BFS.