Depth First Search
Prereq: Recursion Review
With a solid understanding of recursion under our belt, we are now ready to tackle one of the most useful technique 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
def dfs(root, target): if root is None: return None if root.val == target: return root # return non-null return value from the recursive calls left = dfs(root.left, target) if left is not None: return left # at this point, we know left is null, and right could be null or non-null # we return right child's recursive call result directly because # - if it's non-null we should return it # - if it's null, then both left and right are null, we want to return null return dfs(root.right, target) # the code can be shortened to: return dfs(root.left, target) or dfs(root.right, target)
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 and visit the other child
4) is called backtracking. Backtracking and DFS are similar concept 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.right), and return based on results from the recursive calls. This is also a divide and conquer algorithm, i.e. splitting into subroblems 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
DFS is essentially pre-order tree traversal.
- Traverse and find/create/modify/delete node
- Traverse with return value (finding max subtree, detect balanced tree)
DFS/backtracking and combinatorial problems are a match made in heaven (or silver bullet and 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
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 avoiding re-visiting them and going into an infinite loop.
- Find a path from point A to B
- Find connected components
- Detect cycles
- Robert Sedgewick and Kevin Wayne. Algorithms, 4th Edition.
- Steve Skiena. The Algorithm Design Manual, 2nd Edition.
- Richard E. Neapolitan. Foundations of Algorithms, 5th Edition.