Codecademy Logo

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