In programming there are many ways to organize data and one of them is using a tree. A tree is made up of nodes and edges where the edge is what connects two nodes. Using a tree there are different ways to look through them, one of which is depth first search.

Depth first search is one searching algorithms used to search for a node in a tree. It goes down one child node (usually the first one) until it reaches a node with no child then it backtracks until it gets to a node with a child. It repeats those steps until it finds what it is looking for or until it has visited every node. It is easier explained visually:

Image for post
Image for post
https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

Applications

Some real world applications of depth first search include maze generation, cycle detection and path finding.

Image for post
Image for post
https://brilliant.org/wiki/depth-first-search-dfs/

For path finding you can imagine each square as a node and each possible step between two squares as an edge. It basically goes as far down a path as it goes, backtracks if it reaches a dead end then picks the next possible path.

Performance

The run time of depth first search is O(V + E) where V is the number of nodes and E of edges. Worst case scenario is going through the entire tree (visiting all nodes and edges) without finding the node. Depth first search is often compared to breadth first search which looks at all the nodes on one level before moving down to the next. It is better to use depth first search if you think the node is further down the tree.

Written by

Hi

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