# 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*.## Iterative implementation in Python

## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard