Depth-First Search Visualization

What is Depth-First Search?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure, which can be explicitly implemented or implicitly managed via recursive function calls. The algorithm begins at a specified starting node, marks it as visited, and explores its first unvisited neighbor. This process continues recursively, diving deeper into the graph until a dead-end (node with no unvisited neighbors) is reached. At this point, the algorithm backtracks to explore alternative paths. This "depth-first" approach ensures that all nodes connected to the starting node are visited before moving to unrelated parts of the graph.

DFS has numerous applications in computer science. It is widely used in pathfinding problems, such as navigating a maze or solving puzzles. It is also essential for cycle detection in graphs, topological sorting for dependency resolution, and connected component analysis to identify distinct subgraphs. In artificial intelligence, DFS is employed for exhaustive state-space searches, such as solving n-queens problems or traversing decision trees. The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges, as it explores each node and edge once. The space complexity depends on the graph's structure and traversal depth: O(V) for recursive implementations (stack overhead) and O(E) for adjacency list storage. DFS is versatile, working for both directed and undirected graphs, making it a cornerstone algorithm in graph theory and beyond.

DFS Algorithm Pseudocode

            
            DFS(node):
                if node is NULL:
                    return
                mark node as visited
                for each neighbor in node.children:
                    if neighbor is not visited:
                        DFS(neighbor)

Common Trends in Graph Problems where DFS is Applied

Recursive Nature: Many problems can be solved by breaking them into smaller subproblems, making recursion a natural fit.
State Tracking: Keep track of visited nodes, current path, or accumulated values for problems like finding paths or sums.
Base Cases: Clearly define when traversal should stop, such as when reaching a leaf node or a visited node.
Backtracking: Undo changes made during a path when exploring other possibilities, especially in puzzles or pathfinding problems.
Cycle Detection: Use techniques like recursion stacks for detecting cycles in directed graphs.

DFS Framework

Start at the root or specified node and mark it as visited.
Use recursion or a stack to explore neighbors or children.
Implement clear base cases to handle stopping conditions.
Track necessary state, like visited nodes or current path.
Use backtracking when exploring all possible solutions is required.

Popular LeetCode Questions Using DFS

104. Maximum Depth of Binary Tree

Problem:

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution:

This problem uses a Depth-First Search (DFS) approach to calculate the maximum depth of a binary tree. The idea is to recursively determine the depth of the left and right subtrees and then return the greater of the two depths, incremented by one to account for the current node. The base case occurs when the function encounters a null node (indicating an empty subtree), in which case it returns a depth of zero.

This approach ensures that all nodes in the binary tree are visited once, making it efficient. The time complexity of this solution is O(N), where N is the number of nodes in the tree. The space complexity is O(H), where H is the height of the tree, as the recursion stack can grow up to the depth of the tree. This problem highlights the use of recursion for solving tree traversal problems and provides an excellent foundation for understanding divide-and-conquer strategies in tree-based algorithms.

                
                    # Definition for a binary tree node.
                    # class TreeNode:
                    #     def __init__(self, val=0, left=None, right=None):
                    #         self.val = val
                    #         self.left = left
                    #         self.right = right

                    class Solution:
                        def maxDepth(self, root: Optional[TreeNode]) -> int:
                            if not root:
                                return 0
                            
                            left = self.maxDepth(root.left)
                            right = self.maxDepth(root.right)
                    
                            return 1 + max(left,right)

112. Path Sum

Problem:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Solution:

This problem uses a Depth-First Search (DFS) approach to recursively traverse the binary tree. The key idea is to check, at every node, whether the remaining target sum can be achieved along a root-to-leaf path. A node is considered a "leaf" if it has no left or right children. The base case checks if the tree is empty (returning False) or if the current node is a leaf and its value matches the remaining targetSum (returning True).

For non-leaf nodes, the algorithm recursively calls itself on the left and right subtrees, subtracting the current node's value from the remaining targetSum. If any of these recursive calls return True, the function concludes that a valid path exists. This ensures that all possible root-to-leaf paths are explored, making the solution comprehensive. The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once. The space complexity is O(H), where H is the height of the tree, due to the recursive call stack.

                
                    # Definition for a binary tree node.
                    # class TreeNode:
                    #     def __init__(self, val=0, left=None, right=None):
                    #         self.val = val
                    #         self.left = left
                    #         self.right = right
                    class Solution:
                        def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
                            if not root:
                                return False
                            if not root.left and not root.right:
                                return root.val == targetSum
                            
                            left = self.hasPathSum(root.left, targetSum - root.val)
                            right = self.hasPathSum(root.right, targetSum - root.val)

                            return left or right