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.
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 pathfor child in root.children:path_found = dfs(child, target, path)if path_found is not None:return path_foundreturn None
The most concise and efficient DFS implementations use a stack, either explicitly (iterative implementation) or implicitly (call stack from recursion).