# 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

- print node value
- recurse left
- recurse right

```
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

- recurse left
- print node value
- recurse right

```
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

- recurse left
- recurse right
- print node value

```
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.