## What is DFS?

Depth-first Search (DFS) is a tree/graph traversal algorithm that explores as far as possible in each branch.

DFS traversal of the tree above would be:

`[0, 1, 3, 4, 2, 5 ,6]`

## DFS applications

Some of the applications of DFS are:

- traversing a explicit tree to find something
- traversing a graph to:
- find topological sort of graphs
- cycle detection in graphs
- find spanning trees

- use backtracking to:
- solve puzzles
- solve combinatorial problems

## Templates

We can simply traverse through the tree/graph using the following templates.

### DFS on binary tree

```
def do_something(root):
pass
def dfs(root):
if not root:
return
do_something(root)
dfs(root.left)
dfs(root.right)
```

### DFS on N-ary tree

```
def do_something(root):
pass
def get_children(root):
pass
def dfs(root):
if not root:
return
do_something(root)
for child in get_children(root):
dfs(child)
```

### DFS on graphs

```
visited = set()
def do_something(root):
pass
def get_neighbors(root):
pass
def dfs(root, visited):
if root in visited:
return
do_something(root)
visited.add(neighbor)
for neighbor in get_neighbors(root):
dfs(neighbor, visited)
```

In addition to simple traversals, we can also pass value up from child to parent (using return value) or pass value down from parent to child (using function parameters).

### Example of passing value up (return value)

Finding max depth of N-ary tree

```
def get_children(root):
pass
def max_depth(root):
if not root:
return 0
depth = 0
for child in get_children(root):
depth = max(depth, max_depth(child))
return depth + 1
```

### Example of passing value down (function parameter)

Print path on a binary tree

```
def dfs_path(root, res):
if not root:
return
res.append(root)
dfs_path(root.left, res)
dfs_path(root.right, res)
```

Backtracking is also a variation of DFS. Backtracking does not explore the whole tree/graph. Instead, backtracking stops exploring branches that cannot lead to a solution.

Backtracking can often be used to solve puzzles or combinatorial problems.

### Backtracking template

```
def condition():
pass
def do_something(root):
pass
def get_children(root):
pass
def backtrack(root):
if not condition():
return
do_something(root)
for child in get_children(root):
backtrack(child)
```

## Top comments (0)