Depth-First Search Complexity
DFS has time and space complexity of
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).