Depth First Search and Simple Recursion

Today we’ll be talking about a technique to search through a tree called Depth First Search. One common implementation of a tree is a binary tree. A binary tree is a data structure consisting of nodes. Each node contains a value and a pointer to the next two nodes in the tree, right and left. A binary tree can be visualized as below:

Binary Tree

There are many ways to search this data structure, and one is Depth First Search (DFS). DFS starts at a node, and searches through the tree one node at a time until it finds a node that points to no child nodes. Once such a node is found, it goes back to the previous visited node and continues searching the other side, again, until it reaches a node pointing to no more children.

In this way, DFS searches every node in the tree until the entire tree is visited. In layman’s terms, you follow the nodes as deep as they go, and once you reach a wall, you backtrack and start again.

Here is some pseudocode for a DFS, making use of a stack and key value pairs to keep track of which nodes are visited:

1. Pick a starting node in the tree and add it to the top of the stack
2. Grab the node on the top of the stack and mark it as visited
3. All of this node’s adjacent nodes which aren’t already marked visited, add to the stack
4. Repeat steps 2 and 3 until there are no nodes left in the stack

There, once these steps are complete, the whole tree has been visited. Notice how we use recursion here in step 4, where the function calls itself until it reaches the base case: the stack is empty.

Next week, I’ll explain Depth First Search’s sibling, Breadth First Search, and how it differs slightly in it’s implementation.