Depth first search (DFS)
Depth first search is an algorithm to visit the nodes of a graph or a tree.
In DFS, we use a stack to track the nodes that we need to visit, and a hash table to track nodes we've visited.
DFS begins at the root node. The algorithm continuously visits a child node until the end of the path.
It then backtracks back up, and explores an unvisited path.
Traverse a binary tree with DFS
Here's an example the depth first search algorithm on a binary tree.
Similarly, a graph can also be traversed with DFS.
Since we use a stack to keep track of the next tree or graph node to visit, it's common to use recursion to execute depth first search.
Recursive implementation in Python
We can search a target number in a binary tree like the one above using a recursive implementation of DFS:
Given a graph as an adjacency list, here's how to perform depth first search recursively.