## DEV Community 👩‍💻👨‍💻 is a community of 915,052 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# DFS Templates in Python

## 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)
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)

#### Head to your account's Settings to...

🌚 Enable dark mode
🔠 Change your default font
📚 Adjust your experience level to see more relevant content