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)