Stack Bash - Master data structures and algorithms

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.
Depth first search
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. 1.Inorder TraversalEasy
  2. 2.Tree SumEasy
  3. 3.Tree HeightEasy
  4. 4.LCAMedium
  5. 5.Max Path SumHard
  6. 6.Search mazeMedium
  7. 7.Number of islandsMedium
  8. 8.Kth SmallestMedium
  9. 9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.