Depth-First Search (DFS)

def tree_dfs(root):
    """Basic tree DFS traversal"""
    if not root:
        return
    
    # Preorder: process before children
    print(root.val)
    
    tree_dfs(root.left)
    
    # Inorder: process between children (BST gives sorted order)
    
    tree_dfs(root.right)
    
    # Postorder: process after children

def graph_dfs(graph, start):
    """DFS on adjacency list graph"""
    visited = set()
    result = []
    
    def dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            dfs(neighbor)
    
    dfs(start)
    return result

def count_islands(grid):
    """Count connected components in a grid"""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        
        grid[r][c] = '0'  # Mark visited
        
        # Explore 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    
    return count

def find_all_paths(graph, start, end):
    """Find all paths from start to end"""
    all_paths = []
    
    def dfs(node, path):
        if node == end:
            all_paths.append(path[:])
            return
        
        for neighbor in graph[node]:
            if neighbor not in path:  # Avoid cycles
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()  # Backtrack
    
    dfs(start, [start])
    return all_paths

def iterative_dfs(graph, start):
    """DFS using explicit stack"""
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
        
        visited.add(node)
        result.append(node)
        
        # Add neighbors in reverse order for correct traversal
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return result

def has_cycle_directed(graph, n):
    """Detect cycle in directed graph using DFS coloring"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    
    def dfs(node):
        color[node] = GRAY  # Currently exploring
        
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:  # Back edge = cycle
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        
        color[node] = BLACK  # Fully explored
        return False
    
    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
    
    return False