Depth First Search
Prereqs: Recursion Review, Trees
With a solid understanding of recursion under our belts, we are now ready to tackle one of the most useful techniques in coding interviews - Depth First Search (DFS). As the name suggests, DFS is a bold search. We go as deep as we can to look for a value, and when there is nothing new to discover, we retrace our steps to find something new. To put it in a term we already know, the pre-order traversal of a tree is DFS. Let's look at a simple problem of searching for a node in a binary tree whose value is equal to target.
1def dfs(root, target):
2 if root is None:
3 return None
4 if root.val == target:
5 return root
6 # return non-null return value from the recursive calls
7 left = dfs(root.left, target)
8 if left is not None:
9 return left
10
11 # at this point, we know left is null, and right could be null or non-null
12 # we return right child's recursive call result directly because
13 # - if it's non-null we should return it
14 # - if it's null, then both left and right are null, we want to return null
15 return dfs(root.right, target)
16 # the code can be shortened to: return dfs(root.left, target) or dfs(root.right, target)
171public static Node dfs(Node root, int target) {
2 if (root == null) {
3 return null;
4 }
5 if (root.val == target) {
6 return root;
7 }
8 // return non-null return value from the recursive calls
9 Node left = dfs(root.left, target)
10 if (left != null) {
11 return left;
12 }
13 // at this point, we know left is null, and right could be null or non-null
14 // we return right child's recursive call result directly because
15 // - if it's non-null we should return it
16 // - if it's null, then both left and right are null, we want to return null
17 return dfs(root.right, target)
18}
191function dfs(root, target) {
2 if (!root) return null;
3 if (root.val === target) return root;
4 // return non-null return value from the recursive calls
5 const left = dfs(root.left, target);
6 if (left != null) return left;
7 const right = dfs(root.right, target);
8 // at this point, we know left is null, and right could be null or non-null
9 // we return right child's recursive call result directly because
10 // - if it's non-null we should return it
11 // - if it's null, then both left and right are null, we want to return null
12 return right;
13}
141Node<int>* dfs(Node<int>* root, int target) {
2 if (root == nullptr) return nullptr;
3 if (root->val == target) return root;
4 // return non-null return value from the recursive calls
5 Node<int>* left = dfs(root->left, target);
6 if (left != nullptr) return left;
7 // at this point, we know left is null, and right could be null or non-null
8 // we return right child's recursive call result directly because
9 // - if it's non-null we should return it
10 // - if it's null, then both left and right are null, we want to return null
11 return dfs(root->right, target);
12}
131func dfs(root *TreeNode, target int) *TreeNode {
2 if root == nil {
3 return nil
4 }
5 if root.Val == target {
6 return root
7 }
8 // Return non-nil return value from the recursive calls
9 left := dfs(root.Left, target)
10 if left != nil {
11 return left
12 }
13 // At this point, we know left is nil, and right could be nil or non-nil
14 // We return the right child's recursive call result directly because
15 // - If it's non-nil, we should return it
16 // - If it's nil, then both left and right are nil, and we want to return nil
17 return dfs(root.Right, target)
18}
19
Being able to visualize recursion and call stack of a DFS function in your mind is extremely important. Please take a minute to make sure you internalize it and come back to this page any time you need to look at it.
The example above also introduces two other concepts, backtracking and divide and conquer. The action of retracing steps (e.g., from 2 we first visited 3 depth first and retraced back to visit the other child 4) is called backtracking. Backtracking and DFS are similar concepts and essentially the same thing since in DFS you always "backtrack" after exploring a deeper node. It's like saying I program computers by doing coding. If we really want to make the distinction, then backtracking is the concept of retracing and DFS is the algorithm that implements it. In computer science textbooks [1,2,3], backtracking is often mentioned and associated with combinatorial search problems. We will do the same in the course.
We have two recursive calls dfs(root.left) and dfs(root.right), and we return based on the results from the recursive calls. This is also a divide and conquer algorithm, i.e. splitting into subproblems of the same type (search in left and right children) until they are simple enough to be solved directly (null nodes or found target) and combine the results from these subproblems (return non-null node). We'll investigate divide and conquer more in a later module.
When to use DFS
Tree
DFS is essentially pre-order tree traversal.
- Traverse and find/create/modify/delete node
- Traverse with return value (finding max subtree, detect balanced tree)
Combinatorial problems
DFS/backtracking and combinatorial problems are a match made in heaven (or a silver bullet and a werewolf 😅). As we will see in the Combinatorial Search module, combinatorial search problems boil down to searching in trees.
- How many ways are there to arrange something
- Find all possible combinations of ...
- Find all solutions to a puzzle
Graph
Trees are special graphs that have no cycle. We can still use DFS in graphs with cycles. We just have to record the nodes we have visited and avoid re-visiting them and going into an infinite loop.
- Find a path from point A to B
- Find connected components
- Detect cycles
References
- Robert Sedgewick and Kevin Wayne. Algorithms, 4th Edition.
- Steve Skiena. The Algorithm Design Manual, 2nd Edition.
- Richard E. Neapolitan. Foundations of Algorithms, 5th Edition.