depth first search

🏠

A depth first search is very simple to understand and implement, although i'm often surprised to see some developers are unable to perform a pre-order, in-order or post-order search by hand.

A Depth First Search can be performed on trees, and as well graphs. To keep things simple, let's look at a DFS on a binary tree.

 1class Node:
 2    def __init__(self, val=-1, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6        
 7tree = Node('a', 
 8        Node('b', 
 9            Node('c', Node('d'), Node('e')),
10            Node('f', Node('g'), Node('h'))), 
11        Node('i', 
12            Node('j', Node('k'), Node('l')), 
13            Node('m', Node('n'), Node('o'))))

Pre-Order Traversal

In a pre-order traversal, we do a DFS, but print the node value before recursing into the left and right nodes. i.e

1def pre_order(node):
2    if node:
3        print(node.val, end=' ')
4        pre_order(node.left)
5        pre_order(node.right)
6
7pre_order(tree)

In-Order Traversal

In an in-order traversal, we do a DFS, but print the node value between recursing into the left and right nodes. i.e

1def in_order(node):
2    if node:
3        in_order(node.left)
4        print(node.val, end=' ')
5        in_order(node.right)
6
7in_order(tree)

Post-Order Traversal

In an post-order traversal, we do a DFS, but print the node value after recursing into the left and right nodes. i.e

1def post_order(node):
2    if node:
3        post_order(node.left)
4        post_order(node.right)
5        print(node.val, end=' ')
6
7post_order(tree)

Worst time complexity is , worst space complexity of . A DFS is very often employed to solve a wide variety of tree and graph problems. You'll see many examples of DFS being used in this course.

The DFS variants presented on this page are recursive, and are as such very succinct to code up.