Tree Traversal: Breadth-First Search and Depth-First Search

Depth-First Search Complexity

DFS has time and space complexity of O(n).

DFS Implementations

DFS is an exhaustive search algorithm for searching tree data structures that can be implemented with a recursive approach or an iterative one.

Depth-First Search Algorithm

Our depth-first search algorithm was implemented using recursion. The implementation returns the path to the first TreeNode encountered with the matching target value.

def dfs(root, target, path=()):
  path = path + (root,)

  if root.value == target:
    return path

  for child in root.children:
    path_found = dfs(child, target, path)

    if path_found is not None:
      return path_found

  return None

Depth-First Search and Stacks

The most concise and efficient DFS implementations use a stack, either explicitly (iterative implementation) or implicitly (call stack from recursion).