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:

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def dfs(node: BinaryTreeNode, target: int) -> bool:
    if not node:
        return False

    if target == node.data:
        return True

    return dfs(node.left, target) or dfs(node.right, target)


node1 = BinaryTreeNode(1)
node2 = BinaryTreeNode(2)
node3 = BinaryTreeNode(3)
node4 = BinaryTreeNode(4)
node5 = BinaryTreeNode(5)
node6 = BinaryTreeNode(6)
node7 = BinaryTreeNode(7)
node8 = BinaryTreeNode(8)

root = node1

node1.left = node2
node1.right = node3
node2.left = node4
node4.right = node5
node3.left = node7
node3.right = node8

print('Does 8 exist in tree?', dfs(root, 8))
print('Does 23 exist in tree?', dfs(root, 23))

1class BinaryTreeNode:
2    def __init__(self, data):
3        self.data = data
4        self.left = None
5        self.right = None
6
7
8def dfs(node: BinaryTreeNode, target: int) -> bool:
9    if not node:
10        return False
11
12    if target == node.data:
13        return True
14
15    return dfs(node.left, target) or dfs(node.right, target)
16
17
18node1 = BinaryTreeNode(1)
19node2 = BinaryTreeNode(2)
20node3 = BinaryTreeNode(3)
21node4 = BinaryTreeNode(4)
22node5 = BinaryTreeNode(5)
23node6 = BinaryTreeNode(6)
24node7 = BinaryTreeNode(7)
25node8 = BinaryTreeNode(8)
26
27root = node1
28
29node1.left = node2
30node1.right = node3
31node2.left = node4
32node4.right = node5
33node3.left = node7
34node3.right = node8
35
36print('Does 8 exist in tree?', dfs(root, 8))
37print('Does 23 exist in tree?', dfs(root, 23))
38

Given a graph as an adjacency list, here's how to perform depth first search recursively.

graph = {
    'A': ['B', 'D'],
    'B': ['D', 'F'],
    'C': ['A', 'E'],
    'D': ['B', 'C', 'F'],
    'E': ['D', 'F'],
    'F': [],
}

starting_node = 'A'


def dfs(node, visited):
    visited.add(node)
    print('Visited ', node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(neighbour, visited)


print("Recursive Depth First Search")
visited = set()
dfs(starting_node, visited)

1graph = {
2    'A': ['B', 'D'],
3    'B': ['D', 'F'],
4    'C': ['A', 'E'],
5    'D': ['B', 'C', 'F'],
6    'E': ['D', 'F'],
7    'F': [],
8}
9
10starting_node = 'A'
11
12
13def dfs(node, visited):
14    visited.add(node)
15    print('Visited ', node)
16    for neighbour in graph[node]:
17        if neighbour not in visited:
18            dfs(neighbour, visited)
19
20
21print("Recursive Depth First Search")
22visited = set()
23dfs(starting_node, visited)
24

Iterative implementation in Python

import collections

graph = {
    'A': ['B', 'D'],
    'B': ['D', 'F'],
    'C': ['A', 'E'],
    'D': ['B', 'C', 'F'],
    'E': ['D', 'F'],
    'F': [],
}

starting_node = 'A'


def dfs():
    stack = []
    stack.append(starting_node)
    visited = set(starting_node)
    while stack:
        node = stack.pop()
        print('visiting', node)
        visited.add(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                stack.append(neighbour)


print("Iterative Depth First Search")
dfs()

1import collections
2
3graph = {
4    'A': ['B', 'D'],
5    'B': ['D', 'F'],
6    'C': ['A', 'E'],
7    'D': ['B', 'C', 'F'],
8    'E': ['D', 'F'],
9    'F': [],
10}
11
12starting_node = 'A'
13
14
15def dfs():
16    stack = []
17    stack.append(starting_node)
18    visited = set(starting_node)
19    while stack:
20        node = stack.pop()
21        print('visiting', node)
22        visited.add(node)
23        for neighbour in graph[node]:
24            if neighbour not in visited:
25                stack.append(neighbour)
26
27
28print("Iterative Depth First Search")
29dfs()
30

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

Want to confidently pass your next coding interview?

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