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:

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.



Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store