Depth-first search (DFS) explores one path as far as possible, reaching a leaf before backtracking to another branch. A LIFO stack keeps track of where to continue. section 1.4.4 section 1.5
Searching for 8
Starting at root 5, DFS follows the first path down to a leaf. If 8 is not there, it returns to the nearest intersection and explores another path, continuing until it finds 8. section 1.4.4
In a tree, DFS takes O(V) time and uses space bounded by the tree’s depth, O(D). In a graph, track visited nodes to avoid cycles; graph traversal takes O(V + E). section 1.5
Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.
Compare DFS’s deep path with breadth-first search’s layer-by-layer sweep. section 1.4.4








