Depth-First Search

Use Cases

Use Case	Description	Example
Preorder Traversal of a Binary Tree	Given a binary tree, return the values of its nodes in preorder (root, left, right) traversal.	For the tree: 1, with children 2 and 3, and 2's children 4 and 5. The result is [1, 2, 4, 5, 3].
Finding All Paths from Root to Leaves	Find all paths from the root to each leaf node in the binary tree.	For the tree: 1 with children 2 and 3, and 2's children 4 and 5. The result is [[1, 2, 4], [1, 2, 5], [1, 3]].
Checking for Symmetry of a Binary Tree	Check if the binary tree is symmetric around its center.	For the tree: 1 with children 2 and 2 (both having children 3 and 3). The result is True (symmetric).

Code Template

Basic case

dfs() takes two parameters: root (the current node) and result (a list to store node values).
if not root: checks if the current node is None. If it is, the function returns immediately.

Collect node value

It collects node values during the DFS traversal, helping to track the order of processed nodes.

Loop over queue

Recursively calls dfs() on each child, allowing traversal of both subtrees.

def dfs(root, result):
    if not root:
        return

Common mistakes

Wrong Base Case

# Wrong: missing base case
def dfs(root, result):
    result.append(root.val)  # Will fail on None
# Wrong: wrong return value
def dfs(root, result):
    if not root:
        return result  # Should return None
# Correct:
if not root:
    return

Issues and consideration

BFS VS DFS: BFS is ideal for scenarios where you need the shortest path or to explore nodes level by level. DFS is better suited for problems that require exploring all possible options or paths, especially when the solution is deep in the tree or graph.

110. Balanced Binary Tree

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # -1 indicates unbalanced subtree
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            
            return max(left, right) + 1
            
        return dfs(root) != -1

144. Binary Tree Preorder Traversal

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(node):
            if not node:
                return
            result.append(node.val)
            for child in (node.left, node.right):
                dfs(child)
                
        result = []
        dfs(root)
        return result

112. Path Sum

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def dfs(node, currentSum):
            if not node:
                return False
            currentSum += node.val  # Add current node's value
            
            # Check if it's a leaf node and sum matches
            if not node.left and not node.right:
                return currentSum == targetSum
            
            # Continue DFS on children
            for child in (node.left, node.right):
                if dfs(child, currentSum):
                    return True
            return False

        return dfs(root, 0)

200. Number of Islands

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(r, c):
            if (r < 0 or r >= rows or 
                c < 0 or c >= cols or 
                grid[r][c] != '1'):
                return
            # Mark as visited
            grid[r][c] = '#'
            # Visit all adjacent cells
            for nr, nc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                dfs(nr, nc)

        if not grid:
            return 0
            
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
                    
        return count

543. Diameter of Binary Tree

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            # Update diameter if path through current node is longer
            self.diameter = max(self.diameter, left + right)
            
            # Return height of current subtree
            return max(left, right) + 1
            
        self.diameter = 0
        dfs(root)
        return self.diameter

Depth-First Search

Use Cases

Code Template

Basic case

Collect node value

Loop over queue

Common mistakes

Issues and consideration

Related Problem