# DFS (Depth-First Search)

# Overview

Depth-First Search (DFS) is a graph/tree traversal algorithm that explores as far as possible along each branch before backtracking. It uses recursion or a stack to maintain the traversal path.

# Key Properties

• Time Complexity: O(V + E) for graphs, O(n) for trees
• Space Complexity: O(h) for recursion stack, where h = height
• Core Idea: Go deep before going wide
• Data Structure: Stack (implicit via recursion or explicit)
• When to Use: Path finding, cycle detection, topological sort, tree traversal, backtracking problems

# References

• DFS Visualization
• DFS vs BFS Comparison
• Tree Traversal Animations

# Problem Categories

# Pattern 1: Tree Traversal

• Description: Visit all nodes in specific order (preorder, inorder, postorder)
• Recognition: “Traverse”, “visit all”, “print tree”, “serialize”
• Examples: LC 94, LC 144, LC 145, LC 297, LC 449
• Template: Use Tree Traversal Template

# Pattern 2: Path Problems

• Description: Find paths with specific properties in trees/graphs
• Recognition: “Path sum”, “root to leaf”, “all paths”, “longest path”
• Examples: LC 112, LC 113, LC 257, LC 124, LC 543
• Template: Use Path Template with backtracking

# Pattern 3: Graph Traversal

• Description: Explore graphs, find components, detect cycles
• Recognition: “Connected components”, “islands”, “cycle detection”
• Examples: LC 200, LC 695, LC 133, LC 207, LC 210
• Template: Use Graph DFS Template

# Pattern 4: Backtracking

• Description: Try all possibilities, undo choices
• Recognition: “All combinations”, “permutations”, “subsets”
• Examples: LC 46, LC 78, LC 39, LC 17
• Template: Use Backtracking Template

# Pattern 5: Tree Modification

• Description: Modify tree structure or values during traversal
• Recognition: “Delete”, “insert”, “trim”, “convert”
• Examples: LC 450, LC 701, LC 669, LC 538
• Template: Use Modification Template

# Pattern 6: Subtree Problems

• Description: Process subtrees and aggregate results
• Recognition: “Subtree sum”, “duplicate subtrees”, “LCA”
• Examples: LC 508, LC 652, LC 236, LC 663
• Template: Use Bottom-up Template

# Pattern 7: Boundary Elimination (2-Pass DFS)

• Description: Eliminate boundary-connected cells first, then process interior
• Recognition: “Closed islands”, “surrounded regions”, “captured pieces”
• Examples: LC 1254, LC 130, LC 417
• Template: Use 2-Pass DFS Template

# Pattern 8: Path Signatures (Shape Encoding)

• Description: Encode the shape/structure of islands or subtrees using unique path signatures
• Recognition: “Distinct islands”, “unique shapes”, “count different structures”, “same shape after translation”
• Key Technique: Record directional movements during DFS traversal to create a canonical signature
• Examples: LC 694, LC 711, LC 652
• Template: Use Path Signature Template
• Important Notes:
  • Canonical Traversal Order: Always visit neighbors in the same fixed order (e.g., Down, Up, Right, Left)
  • Starting Point Normalization: Start DFS from top-left-most cell to ensure consistent signatures
  • Delimiter Usage: Use delimiters (like ‘O’ for “Out”) when backtracking to distinguish different shapes
  • Relative Encoding: Record relative positions or directional movements, not absolute coordinates

# Pattern 9: DFS with Validation (Sub-Component Detection)

• Description: Traverse one grid/graph structure while validating against another reference structure
• Recognition: “Sub-islands”, “subset validation”, “component matching”, “inclusion checking”
• Key Technique: DFS traversal with boolean flag that tracks whether ALL cells satisfy a condition
• Examples: LC 1905 (Count Sub Islands)
• Template: Use DFS Validation Template
• Important Notes:
  • Boolean Flag Propagation: Use res = dfs(...) && res pattern to accumulate validation results
  • Mark Visited: Mark visited cells in the traversal grid to avoid revisiting
  • Short-circuit Optimization: Can optimize by returning early if validation fails
  • Two-Grid Comparison: One grid for traversal structure, another for validation condition

# Pattern 10: Bidirectional Graph with Direction Tracking

• Description: Build undirected graph representation of a directed graph, track original edge directions during DFS traversal
• Recognition: “Reorder edges”, “reverse routes”, “make paths lead to”, “minimum edge reversals”, “orient edges”
• Key Technique: Store direction metadata (flag) for each edge in bidirectional adjacency list, count edges needing reversal during DFS
• Examples: LC 1466 (Reorder Routes to Make All Paths Lead to the City Zero)
• Template: Use Bidirectional Direction Tracking Template
• Important Notes:
  • Bidirectional Graph Construction: Add both directions for each edge, but mark original direction with flag
  • Direction Flag: Use 1 for edges in original direction, 0 for reverse direction
  • Count During Traversal: Increment counter when traversing an edge with flag=1 (wrong direction)
  • Tree Property: Works well with tree structures (n-1 edges for n nodes)
  • From Root: Always start DFS from the target node (the node all paths should lead to)

# Pattern 11: Component Pair Counting (Unreachable Pairs)

• Description: Count pairs of nodes that cannot reach each other in a graph with multiple disconnected components
• Recognition: “Unreachable pairs”, “count disconnected pairs”, “pairs in different components”, “isolated node pairs”
• Key Technique: Find all components using DFS/Union-Find, then count pairs between different components using cumulative multiplication
• Examples: LC 2316 (Count Unreachable Pairs of Nodes in an Undirected Graph)
• Template: Use Component Pair Counting Template
• Important Notes:
  • Two Counting Approaches:
    • Forward: componentSize × nodesProcessed (nodes already seen)
    • Backward: componentSize × (n - componentSize - processed) (remaining nodes)
  • Avoid Double Counting: Only count pairs between different components once
  • Mathematical Optimization: O(components) instead of O(n²) brute force
  • Component Discovery: Use DFS or Union-Find to identify all components
  • Cumulative Tracking: Keep running sum of processed nodes to calculate pairs efficiently

# Templates & Algorithms

# Template Comparison Table

Template Type	Use Case	Key Operation	Time	Space	When to Use
Tree Traversal	Visit all nodes	Recursive/Stack	O(n)	O(h)	Tree problems
Graph DFS	Explore graph	Visited set	O(V+E)	O(V)	Graph exploration
Backtracking	Try all paths	Undo choices	O(b^d)	O(d)	Combinatorial
Path Finding	Find specific paths	Track path	O(n)	O(h)	Path problems
Modification	Change structure	Update nodes	O(n)	O(h)	Tree editing
Bottom-up	Aggregate info	Post-order	O(n)	O(h)	Subtree problems
2-Pass DFS	Boundary elimination	Two-phase flood	O(m×n)	O(m×n)	Closed/surrounded regions
Path Signature	Encode shapes	Directional tracking	O(m×n)	O(m×n)	Distinct shape counting
DFS Validation	Component validation	Boolean flag propagation	O(m×n)	O(m×n)	Sub-component detection
Bidirectional Direction	Track edge direction	Bidirectional + flags	O(V+E)	O(V+E)	Edge reorientation/reversal
Component Pair Counting	Count unreachable pairs	Cumulative multiplication	O(V+E)	O(V)	Disconnected component pairs

# Universal DFS Template

def dfs(node, visited=None):
    """
    Universal DFS template for trees and graphs
    Can be adapted for various problems
    """
    # Base case
    if not node or (visited and node in visited):
        return
    
    # Mark as visited (for graphs)
    if visited is not None:
        visited.add(node)
    
    # Process current node (pre-order position)
    process(node)
    
    # Recursive calls
    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)
    
    # Post-order processing if needed
    # process_after(node)

# Template 1: Tree Traversal

# Preorder: Root -> Left -> Right
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Inorder: Left -> Root -> Right  
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Postorder: Left -> Right -> Root
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative with Stack
def dfs_iterative(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Add right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

# Template 2: Graph DFS

def dfs_graph(graph, start):
    """
    DFS for graph with cycle handling
    """
    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

# For detecting cycles
def has_cycle(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

# Template 3: Path Finding

def find_paths(root, target):
    """
    Find all root-to-leaf paths with sum = target
    """
    def dfs(node, curr_sum, path, result):
        if not node:
            return
        
        # Update current state
        curr_sum += node.val
        path.append(node.val)
        
        # Check if leaf and target met
        if not node.left and not node.right:
            if curr_sum == target:
                result.append(path[:])
        
        # Explore children
        dfs(node.left, curr_sum, path, result)
        dfs(node.right, curr_sum, path, result)
        
        # Backtrack
        path.pop()
    
    result = []
    dfs(root, 0, [], result)
    return result

# Template 4: Backtracking

def backtrack_template(candidates, target):
    """
    General backtracking template
    """
    def backtrack(start, path, remaining):
        # Base case - found solution
        if remaining == 0:
            result.append(path[:])
            return
        
        # Try all possibilities
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            
            # Make choice
            path.append(candidates[i])
            
            # Recurse
            backtrack(i, path, remaining - candidates[i])
            
            # Undo choice (backtrack)
            path.pop()
    
    result = []
    backtrack(0, [], target)
    return result

# Template 5: Tree Modification

def modify_tree(root, condition):
    """
    Modify tree structure based on condition
    """
    if not root:
        return None
    
    # Recursively modify subtrees first
    root.left = modify_tree(root.left, condition)
    root.right = modify_tree(root.right, condition)
    
    # Modify current node based on condition
    if not condition(root):
        # Example: delete node, return child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Handle two children case
        # ... (find successor/predecessor)
    
    return root

# Template 6: Bottom-up DFS

def bottom_up_dfs(root):
    """
    Process subtrees first, then current node
    Useful for subtree problems
    """
    def dfs(node):
        if not node:
            return 0  # or base value

        # Process subtrees first
        left_result = dfs(node.left)
        right_result = dfs(node.right)

        # Process current node using subtree results
        current_result = process(node, left_result, right_result)

        # Update global result if needed
        self.global_result = max(self.global_result, current_result)

        return current_result

    self.global_result = 0
    dfs(root)
    return self.global_result

# Template 7: 2-Pass DFS (Boundary Elimination)

def two_pass_dfs(grid):
    """
    Two-pass approach for grid problems
    Pass 1: Eliminate boundary-connected cells
    Pass 2: Count/process remaining valid cells
    Common for "closed" or "surrounded" problems
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        """Mark cell and all connected cells as visited"""
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != target:
            return
        grid[r][c] = marked  # Mark as visited
        # Visit 4 neighbors
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # Pass 1: Eliminate boundary-connected cells
    # Top and bottom borders
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)

    # Left and right borders
    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # Pass 2: Count/process remaining valid cells
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == target:
                count += 1
                flood(r, c)  # Mark to avoid double counting

    return count

// Java implementation
public int twoPassDFS(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int rows = grid.length;
    int cols = grid[0].length;

    // Pass 1: Eliminate boundary-connected cells
    for (int c = 0; c < cols; c++) {
        flood(grid, 0, c);           // Top border
        flood(grid, rows - 1, c);    // Bottom border
    }

    for (int r = 0; r < rows; r++) {
        flood(grid, r, 0);           // Left border
        flood(grid, r, cols - 1);    // Right border
    }

    // Pass 2: Count remaining valid cells
    int count = 0;
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);
            }
        }
    }

    return count;
}

private void flood(int[][] grid, int r, int c) {
    int rows = grid.length;
    int cols = grid[0].length;

    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
        return;
    }

    grid[r][c] = 1;  // Mark as visited

    // Visit 4 neighbors
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] dir : dirs) {
        flood(grid, r + dir[0], c + dir[1]);
    }
}

# Template 8: Path Signature (Shape Encoding)

def count_distinct_shapes(grid):
    """
    Count distinct island shapes using path signatures
    Key: Encode each island's shape as a unique string
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    unique_shapes = set()

    def dfs(r, c, r0, c0, path):
        """
        DFS with path signature encoding
        r0, c0: Starting position for relative encoding
        path: StringBuilder to record the shape signature
        """
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        # Mark as visited
        grid[r][c] = 0

        # Encode relative position
        path.append(f"({r - r0},{c - c0})")

        # Visit neighbors in FIXED order (critical for consistency)
        dfs(r + 1, c, r0, c0, path)  # Down
        dfs(r - 1, c, r0, c0, path)  # Up
        dfs(r, c + 1, r0, c0, path)  # Right
        dfs(r, c - 1, r0, c0, path)  # Left

    # Iterate through grid in fixed order (top-left to bottom-right)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, r, c, path)  # Start with (r, c) as origin
                unique_shapes.add(tuple(path))

    return len(unique_shapes)

// Java implementation with directional encoding
public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    Set<String> uniqueIslandShapes = new HashSet<>();
    int rows = grid.length;
    int cols = grid[0].length;

    // Iterate through every cell in the grid
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // Start DFS only on unvisited land cells
            if (grid[r][c] == 1) {
                StringBuilder pathSignature = new StringBuilder();
                // Start DFS from (r, c). 'S' marks the start
                dfs(grid, r, c, pathSignature, 'S');

                if (pathSignature.length() > 0) {
                    uniqueIslandShapes.add(pathSignature.toString());
                }
            }
        }
    }

    return uniqueIslandShapes.size();
}

/**
 * DFS with directional encoding
 * Records the direction taken to reach each cell
 * Uses 'O' delimiter when backtracking
 */
private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base cases: Out of bounds or water/visited
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
        return;
    }

    // 1. Mark as visited by setting to 0
    grid[r][c] = 0;

    // 2. Record the direction taken to reach this cell
    path.append(direction);

    // 3. Recurse in FIXED order (Down, Up, Right, Left)
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // 4. Add delimiter when backtracking
    // This distinguishes different branch structures
    path.append('O');
}

// Alternative: Relative coordinate encoding
public int numDistinctIslands_v2(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Set<String> shapes = new HashSet<>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (!seen[r][c] && grid[r][c] == 1) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, seen, r, c, r, c, sb);
                shapes.add(sb.toString());
            }
        }
    }
    return shapes.size();
}

/**
 * DFS with relative coordinate encoding
 * Records relative positions from starting point
 */
private void dfs(int[][] grid, boolean[][] seen, int r0, int c0, int r, int c, StringBuilder sb) {
    int rows = grid.length, cols = grid[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (seen[r][c] || grid[r][c] != 1) return;

    seen[r][c] = true;
    // Record relative position from origin (r0, c0)
    sb.append((r - r0)).append('_').append((c - c0)).append(',');

    // Visit in fixed order
    dfs(grid, seen, r0, c0, r + 1, c, sb);
    dfs(grid, seen, r0, c0, r - 1, c, sb);
    dfs(grid, seen, r0, c0, r, c + 1, sb);
    dfs(grid, seen, r0, c0, r, c - 1, sb);
}

Key Concepts for Path Signatures:

1. Canonical Traversal Order

   • Always check neighbors in the same fixed sequence (e.g., D, U, R, L)
   • This ensures identical shapes produce identical signatures

2. Starting Point Normalization

   • Grid traversal in fixed order (top-to-bottom, left-to-right)
   • The first land cell encountered becomes the origin
   • All coordinates are relative to this origin

3. Why Delimiters Matter

   Shape 1:  11      Shape 2:   1
              1                11
   
   Without delimiter: "SDRO"  vs "SDRO"  (Same - Wrong!)
   With delimiter:    "SDOO"  vs "SDRO"  (Different - Correct!)
   

4. Consistency Guarantees

   • Same shape → Same signature (always)
   • Different shapes → Different signatures
   • Translation invariant (position doesn’t matter)
   • Rotation/reflection sensitive (as required)

# Template 9: DFS with Validation (Sub-Component Detection)

/**
 * Pattern: DFS traversal on one grid while validating against another grid
 * Use case: Count sub-islands, validate subset components, inclusion checking
 * Key insight: Use boolean flag propagation to track whether ALL cells satisfy condition
 *
 * Time: O(m × n) - visit each cell once
 * Space: O(m × n) - recursion stack + visited set
 */
public int countSubComponents(int[][] grid1, int[][] grid2) {
    if (grid2 == null || grid2.length == 0) {
        return 0;
    }

    int rows = grid2.length;
    int cols = grid2[0].length;
    Set<Integer> visited = new HashSet<>();
    int count = 0;

    // Iterate through grid2 to find all components
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int flatCoord = r * cols + c;

            // Start DFS on unvisited land cells in grid2
            if (grid2[r][c] == 1 && !visited.contains(flatCoord)) {
                // DFS returns true if ALL cells in this component exist in grid1
                if (dfsValidate(grid1, grid2, r, c, visited)) {
                    count++;
                }
            }
        }
    }

    return count;
}

/**
 * DFS with validation: Check if entire component in grid2 is subset of grid1
 * Returns true only if ALL cells in the component satisfy the condition
 */
private boolean dfsValidate(int[][] grid1, int[][] grid2, int r, int c, Set<Integer> visited) {
    int rows = grid2.length;
    int cols = grid2[0].length;
    int flatCoord = r * cols + c;

    // Base cases
    if (r < 0 || r >= rows || c < 0 || c >= cols
        || grid2[r][c] == 0 || visited.contains(flatCoord)) {
        return true; // Empty/visited cells don't violate the condition
    }

    // Mark as visited
    visited.add(flatCoord);

    // Initialize result as true
    boolean isValid = true;

    // Check condition: Does this cell exist in grid1?
    if (grid1[r][c] == 0) {
        isValid = false; // Found a cell in grid2 that's NOT in grid1
    }

    // CRITICAL: Use && with res to propagate validation through entire component
    // Must visit ALL neighbors even if isValid is false (to mark them as visited)
    isValid = dfsValidate(grid1, grid2, r - 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r + 1, c, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c - 1, visited) && isValid;
    isValid = dfsValidate(grid1, grid2, r, c + 1, visited) && isValid;

    return isValid;
}

Python Implementation:

def count_sub_components(grid1, grid2):
    """
    Count components in grid2 that are completely contained in grid1
    """
    if not grid2 or not grid2[0]:
        return 0

    rows, cols = len(grid2), len(grid2[0])
    visited = set()
    count = 0

    def dfs(r, c):
        """
        DFS with validation
        Returns True if entire component is valid
        """
        # Base cases
        if (r < 0 or r >= rows or c < 0 or c >= cols
            or grid2[r][c] == 0 or (r, c) in visited):
            return True

        visited.add((r, c))

        # Check condition
        is_valid = True
        if grid1[r][c] == 0:
            is_valid = False

        # Visit all neighbors (must visit ALL even if invalid)
        is_valid = dfs(r - 1, c) and is_valid
        is_valid = dfs(r + 1, c) and is_valid
        is_valid = dfs(r, c - 1) and is_valid
        is_valid = dfs(r, c + 1) and is_valid

        return is_valid

    # Main loop
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] == 1 and (r, c) not in visited:
                if dfs(r, c):
                    count += 1

    return count

Concrete Example: LC 1905 - Count Sub Islands

Problem: Count islands in grid2 that are completely contained in grid1

grid1: [[1,1,1,0,0],    grid2: [[1,1,1,0,0],
        [0,1,1,1,1],            [0,0,1,0,0],
        [0,0,0,0,0],            [0,1,0,0,0],
        [1,0,0,0,0],            [1,0,1,1,0],
        [1,1,0,1,1]]            [0,1,0,1,0]]

Analysis:
- Island 1 in grid2 (top-left): Cells (0,0), (0,1), (0,2), (1,2)
  → Check grid1: All exist? YES → Count it ✓

- Island 2 in grid2 (middle): Cells (2,1)
  → Check grid1: (2,1) = 0 → NOT a sub-island ✗

- Island 3 in grid2 (bottom): Cells (3,0), (3,2), (3,3), (4,1), (4,3)
  → Check grid1: (3,0) = 1, but (4,1) = 1... complex shape
  → Some cells don't match → NOT a sub-island ✗

Result: 1 sub-island (only the first one)

Key Insight:
- Must traverse ENTIRE island in grid2
- Check EVERY cell against grid1
- Return true only if ALL cells pass validation

Why Boolean Propagation Works:

// CORRECT: Visit all neighbors, accumulate results
res = dfs(r - 1, c) && res;
res = dfs(r + 1, c) && res;
res = dfs(r, c - 1) && res;
res = dfs(r, c + 1) && res;

// WRONG: Short-circuits, doesn't visit all cells
if (!dfs(r - 1, c)) return false;  // Stops early, leaves cells unvisited!

Pattern Characteristics:

• Two Data Sources: One for structure (grid2), one for validation (grid1)
• Complete Traversal: Must visit entire component, cannot short-circuit
• Boolean Accumulation: Use res = dfs(...) && res pattern
• Visited Tracking: Essential to avoid infinite loops and double-counting
• Total Time: O(m × n) - each cell visited once
• Total Space: O(m × n) - recursion stack + visited set

When to Use This Pattern:

• Validate that one component is subset of another
• Check if structure A is completely contained in structure B
• Count valid sub-components with specific properties
• Two-grid comparison problems

Key Variations:

1. Early Termination: Mark entire component as invalid if one cell fails
2. Flip Validation: Check grid2 cells DON’T exist in grid1 (inverse problem)
3. Multiple Grids: Validate against multiple reference grids
4. Weighted Validation: Sum values during traversal, check threshold

Similar Problems:

• LC 1905: Count Sub Islands (two grids, subset validation)
• LC 200: Number of Islands (single grid, basic DFS)
• LC 695: Max Area of Island (single grid, count cells)
• LC 463: Island Perimeter (single grid, count edges)
• LC 827: Making A Large Island (grid modification, max area)

# Template 10: Bidirectional Graph with Direction Tracking

/**
 * Pattern: Build bidirectional graph with direction flags, count edge reversals via DFS
 * Use case: Reorder edges, reverse routes, make all paths lead to a target node
 * Key insight: Treat directed graph as undirected for traversal, but track original directions
 *
 * Time: O(V + E) - visit each node and edge once
 * Space: O(V + E) - adjacency list + visited array
 */
public int minReorder(int n, int[][] connections) {
    // Build bidirectional adjacency list with direction flags
    // Map: city -> List of [neighbor, direction_flag]
    // direction_flag: 1 if original direction (needs reversal)
    // direction_flag: 0 if reverse direction (correct direction)
    Map<Integer, List<int[]>> adj = new HashMap<>();
    for (int i = 0; i < n; i++) {
        adj.put(i, new ArrayList<>());
    }

    for (int[] c : connections) {
        int from = c[0];
        int to = c[1];

        // Original direction: from -> to (flag = 1, needs reversal)
        adj.get(from).add(new int[]{to, 1});

        // Reverse direction: to -> from (flag = 0, correct direction)
        adj.get(to).add(new int[]{from, 0});
    }

    boolean[] visited = new boolean[n];
    int[] count = {0}; // Use array to pass by reference

    // Start DFS from target node (city 0)
    dfsCountReversals(0, adj, visited, count);

    return count[0];
}

/**
 * DFS to count edges that need reversal
 * Increment count when traversing edge with flag=1 (wrong direction)
 */
private void dfsCountReversals(int node, Map<Integer, List<int[]>> adj,
                                boolean[] visited, int[] count) {
    visited[node] = true;

    for (int[] edge : adj.get(node)) {
        int neighbor = edge[0];
        int directionFlag = edge[1];

        if (!visited[neighbor]) {
            // If flag = 1, edge points away from target (needs reversal)
            if (directionFlag == 1) {
                count[0]++;
            }
            dfsCountReversals(neighbor, adj, visited, count);
        }
    }
}

Python Implementation:

def min_reorder(n, connections):
    """
    Count minimum edge reversals to make all paths lead to node 0
    """
    # Build bidirectional graph with direction flags
    adj = {i: [] for i in range(n)}

    for src, dst in connections:
        # Original direction: src -> dst (flag=1, needs reversal)
        adj[src].append((dst, 1))
        # Reverse direction: dst -> src (flag=0, correct)
        adj[dst].append((src, 0))

    visited = set()
    count = [0]

    def dfs(node):
        visited.add(node)

        for neighbor, flag in adj[node]:
            if neighbor not in visited:
                # If flag=1, edge points away from 0 (needs reversal)
                if flag == 1:
                    count[0] += 1
                dfs(neighbor)

    dfs(0)  # Start from target node
    return count[0]

Key Concepts:

1. Bidirectional Graph Construction

   • Add both directions for each edge
   • Original direction gets flag=1 (needs reversal)
   • Reverse direction gets flag=0 (already correct)

2. Why This Works

   Example: connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
   
   Original directed graph (edges point away from 0):
   0 -> 1 -> 3
   2 -> 3
   4 -> 0, 4 -> 5
   
   Need to reverse: 0->1, 1->3, 4->5 (3 reversals)
   
   During DFS from 0:
   - Visit 1: used edge 0->1 (flag=1) → count++
   - Visit 3: used edge 1->3 (flag=1) → count++
   - Visit 2: used edge 2->3 (flag=0) → no count
   - Visit 4: used edge 4->0 (flag=0) → no count
   - Visit 5: used edge 4->5 (flag=1) → count++
   Total = 3
   

3. Direction Flag Logic

   • Flag=1: Edge in original direction (current->neighbor)
     • Means we’re using an edge pointing away from root
     • Must be reversed
   • Flag=0: Edge in reverse direction (neighbor->current)
     • Means original edge pointed toward root
     • Already correct

4. Tree Property

   • Works perfectly for tree structures (n-1 edges)
   • Every node reachable from root
   • No cycles to worry about

Pattern Characteristics:

• Graph Type: Tree or directed graph
• Key Technique: Bidirectional representation with metadata
• DFS Start: Always from target node
• Count Condition: Edges with flag=1 need reversal
• Visited Tracking: Essential for tree traversal
• Time Complexity: O(V + E) - linear
• Space Complexity: O(V + E) - adjacency list

When to Use This Pattern:

• “Reorder routes/edges to make all paths lead to X”
• “Minimum edge reversals to connect all nodes to root”
• “Orient edges so all nodes can reach target”
• Tree/graph problems requiring edge direction changes
• Counting necessary modifications to edge directions

Similar Problems:

• LC 1466: Reorder Routes to Make All Paths Lead to the City Zero
• LC 1568: Minimum Number of Days to Disconnect Island (related graph modification)
• LC 1579: Remove Max Number of Edges to Keep Graph Fully Traversable (edge orientation)

# Template 11: Component Pair Counting (Unreachable Pairs)

/**
 * Pattern: Count pairs of nodes that cannot reach each other across different components
 * Use case: Count unreachable/disconnected pairs, isolated node pairs
 * Key insight: For each component, multiply its size by nodes in OTHER components
 *
 * Time: O(V + E) - DFS to find all components
 * Space: O(V) - visited array + adjacency list
 */

// Approach 1: DFS with Forward Counting (count against already processed)
public long countUnreachablePairs_DFS_Forward(int n, int[][] edges) {
    // Build adjacency list
    List<Integer>[] adj = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<>();
    }
    for (int[] edge : edges) {
        adj[edge[0]].add(edge[1]);
        adj[edge[1]].add(edge[0]);
    }

    boolean[] visited = new boolean[n];
    long totalUnreachablePairs = 0;
    long nodesProcessed = 0; // Track nodes in components already processed

    // Find each component and count pairs
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // DFS to find component size
            long componentSize = dfs(i, adj, visited);

            /**
             * KEY TRICK: Forward counting
             * Each node in current component is unreachable from
             * ALL nodes in previous components
             *
             * Formula: componentSize × nodesProcessed
             * - componentSize: nodes in current component
             * - nodesProcessed: nodes in all previous components
             */
            totalUnreachablePairs += componentSize * nodesProcessed;

            // Update processed count
            nodesProcessed += componentSize;
        }
    }

    return totalUnreachablePairs;
}

private long dfs(int node, List<Integer>[] adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            count += dfs(neighbor, adj, visited);
        }
    }

    return count;
}

// Approach 2: Union-Find with Backward Counting (count against remaining unprocessed)
public long countUnreachablePairs_UnionFind_Backward(int n, int[][] edges) {
    // Initialize Union-Find
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    // Union all edges
    for (int[] edge : edges) {
        union(edge[0], edge[1], parent, rank);
    }

    // Count component sizes
    Map<Integer, Integer> sizeMap = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int root = find(i, parent);
        sizeMap.put(root, sizeMap.getOrDefault(root, 0) + 1);
    }

    long result = 0;
    long processed = 0;

    /**
     * KEY TRICK: Backward counting
     * For each component, count pairs with ALL remaining unprocessed nodes
     *
     * Formula: size × (n - size - processed)
     * - size: nodes in current component
     * - n: total nodes
     * - processed: nodes in components already counted
     * - (n - size - processed): nodes in OTHER components not yet counted
     *
     * This avoids double counting by only counting forward to remaining components
     */
    for (int size : sizeMap.values()) {
        result += size * (n - size - processed);
        processed += size;
    }

    return result;
}

private int find(int x, int[] parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent); // Path compression
    }
    return parent[x];
}

private void union(int x, int y, int[] parent, int[] rank) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);

    if (rootX != rootY) {
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Approach 3: Alternative - Count total pairs minus reachable pairs
public long countUnreachablePairs_Alternative(int n, int[][] edges) {
    // Build adjacency list
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    /**
     * Total possible pairs = n × (n-1) / 2
     * Reachable pairs = sum of (componentSize × (componentSize-1) / 2) for each component
     * Unreachable pairs = Total - Reachable
     */
    long totalPairs = (long) n * (n - 1) / 2;
    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            long size = dfsCount(i, adj, visited);
            // Subtract reachable pairs within this component
            totalPairs -= (size * (size - 1)) / 2;
        }
    }

    return totalPairs;
}

private long dfsCount(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    long count = 1;

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            count += dfsCount(neighbor, adj, visited);
        }
    }

    return count;
}

Python Implementation:

def count_unreachable_pairs_dfs(n, edges):
    """
    Count unreachable pairs using DFS with forward counting
    """
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    total_pairs = 0
    processed = 0

    def dfs(node):
        """DFS to count component size"""
        visited[node] = True
        count = 1
        for neighbor in adj[node]:
            if not visited[neighbor]:
                count += dfs(neighbor)
        return count

    # Find each component
    for i in range(n):
        if not visited[i]:
            component_size = dfs(i)

            # Key trick: multiply by already processed nodes
            total_pairs += component_size * processed
            processed += component_size

    return total_pairs


def count_unreachable_pairs_uf(n, edges):
    """
    Count unreachable pairs using Union-Find with backward counting
    """
    # Initialize Union-Find
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x != root_y:
            parent[root_x] = root_y

    # Union all edges
    for u, v in edges:
        union(u, v)

    # Count component sizes
    from collections import Counter
    size_map = Counter(find(i) for i in range(n))

    result = 0
    processed = 0

    # Key trick: count against remaining unprocessed nodes
    for size in size_map.values():
        result += size * (n - size - processed)
        processed += size

    return result

Key Concepts:

1. Two Counting Approaches

   Forward Counting (Approach 1):
   - Component 1 (size=3): 3 × 0 = 0
   - Component 2 (size=2): 2 × 3 = 6
   - Component 3 (size=4): 4 × 5 = 20
   - Total: 26
   
   Backward Counting (Approach 2):
   - Component 1 (size=3): 3 × (9-3-0) = 18
   - Component 2 (size=2): 2 × (9-2-3) = 8
   - Component 3 (size=4): 4 × (9-4-5) = 0
   - Total: 26
   
   Both give same result, different order of calculation
   

2. Why This Works

   • Nodes in different components CANNOT reach each other
   • Each pair of nodes from different components = 1 unreachable pair
   • Multiplication counts all such cross-component pairs efficiently
   • Avoid O(n²) brute force by tracking cumulative counts

3. Visualization

   Example: n=7, components=[3,2,2]
   
   Component A: {0,1,2}  (size=3)
   Component B: {3,4}     (size=2)
   Component C: {5,6}     (size=2)
   
   Unreachable pairs:
   - A-B: 3×2 = 6 pairs
   - A-C: 3×2 = 6 pairs
   - B-C: 2×2 = 4 pairs
   Total: 16 pairs
   
   Forward: 3×0 + 2×3 + 2×5 = 0+6+10 = 16 ✓
   Backward: 3×4 + 2×2 + 2×0 = 12+4+0 = 16 ✓
   

4. Common Pitfalls

   • Double Counting: Must only count each pair once
   • Component Discovery: Must visit ALL nodes to find all components
   • Overflow: Use long for large n (up to 10^5 nodes → ~10^10 pairs)
   • Edge Cases: Single component (return 0), no edges (return n×(n-1)/2)

Pattern Characteristics:

• Graph Type: Undirected graph with multiple components
• Key Insight: Unreachable = different components
• Optimization: Cumulative multiplication instead of nested loops
• Component Finding: DFS, BFS, or Union-Find all work
• Time Complexity: O(V + E) - linear in graph size
• Space Complexity: O(V) - visited tracking or parent array

When to Use This Pattern:

• “Count pairs of nodes that cannot reach each other”
• “Number of unreachable/disconnected node pairs”
• “Pairs from different components”
• “Isolated groups” with pair counting
• Graph connectivity with counting requirement

Similar Problems:

• LC 2316: Count Unreachable Pairs of Nodes in an Undirected Graph
• LC 323: Number of Connected Components in an Undirected Graph (component counting)
• LC 547: Number of Provinces (similar component detection)
• LC 684: Redundant Connection (Union-Find with components)
• LC 1135: Connecting Cities With Minimum Cost (MST with component awareness)

Variations:

1. Weighted Pairs: Count with node weights instead of simple counting
2. Conditional Pairs: Only count pairs satisfying additional constraints
3. Dynamic Components: Add/remove edges and update count incrementally
4. K-Component Pairs: Count pairs from components of specific size k

---

• Assign sub tree to node, then return updated node at final stage (Important !!!)

// java
// LC 199
private TreeNode _dfs(TreeNode node){

    if (node == null){
        return null;
    }

    /** NOTE !!! no need to create global node, but can define inside the method */
    TreeNode root2 = node;
    root2.left = this._dfs(node.left);
    root2.right = this._dfs(node.right);

    /** NOTE !!! we need to return root as final step */
    return root2;
}

• Modify tree in place (Important !!!)

// java
// LC 701

// ...
public TreeNode insertIntoBST(TreeNode root, int val){
    // ...

    insertNodeHelper(root, val);
    return root;
}

public void insertNodeHelper(TreeNode root, int val) {
    // ...
    if(...){
        root.left = new TreeNode(val);
    }else{
        root.right = new TreeNode(val);
    }

    // ...
    return root;
}

// ... 

• Tree transversal (DFS)

# python
# form I : tree transversal
def dfs(root, target):

    if root.val == target:
       # do sth

    if root.val < target:
       dfs(root.left, target)
       # do sth

    if root.val > target:
       dfs(root.right, target)
       # do sth

• Tree value moddify (DFS)

# form II : modify values in tree

# 669 Trim a Binary Search Tree
class Solution:
    def trimBST(self, root, L, R):
        if not root:
            return 
        # NOTICE HERE 
        # SINCE IT'S BST
        # SO if root.val < L, THE root.right MUST LARGER THAN L
        # SO USE self.trimBST(root.right, L, R) TO FIND THE NEXT "VALIDATE" ROOT AFTER TRIM
        # THE REASON USE self.trimBST(root.right, L, R) IS THAT MAYBE NEXT ROOT IS TRIMMED AS WELL, SO KEEP FINDING VIA RECURSION
        if root.val < L:
            return self.trimBST(root.right, L, R)
        # NOTICE HERE 
        # SINCE IT'S BST
        # SO if root.val > R, THE root.left MUST SMALLER THAN R
        # SO USE self.trimBST(root.left, L, R) TO FIND THE NEXT "VALIDATE" ROOT AFTER TRIM
        if root.val > R:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root 

# 701 Insert into a Binary Search Tree
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        NOTE !!!
            1) we ALWAYS do op first, then do recursive
                -> e.g.
                        ...
                        if not root: 
                            return TreeNode(val)
                        if root.val < val:
                            root.right = self.insertIntoBST(root.right, val)
                        ...
        """
        if not root: 
            return TreeNode(val)

        if root.val < val: 
            root.right = self.insertIntoBST(root.right, val)

        elif root.val > val: 
            root.left = self.insertIntoBST(root.left, val)

        return root

# form III : check if a value exist in the BST

def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    if root.val > value:
        return dfs(root.left, value) 
    if root.val < value:
        return dfs(root.right, value)

# form IV : check if duplicated nodes in tree
# LC 652
# python
m = collections.defaultdict(int)
# m is collection for record visited nodes
def dfs(root, m, res):
    if not root:
        return "#"

    ### NOTE : we get path via below, so we can know duplicated nodes
    path = root.val + "-" + self.dfs(root.left, m, res) + "-" + self.dfs(root.right, m, res)

    if m[path] == 1:
        res.append(path)

    m[path] += 1
    return path

• Grpah transversal (DFS)

• Transversal in 4 directions (up, down, left, right)

// java
// LC 200

/** NOTE !!!! BELOW approach has same effect */

// V1

// private boolean _is_island(char[][] grid, int x, int y, boolean[][] seen){}

// ....
_is_island(grid, x+1, y, seen);
_is_island(grid, x-1, y, seen);
_is_island(grid, x, y+1, seen);
_is_island(grid, x, y-1, seen);
// ....

// V2
// private boolean _is_island_2(char[][] grid, int x, int y, boolean[][] seen) {}

int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

for (int[] dir : directions) {
    int newX = x + dir[0];
    int newY = y + dir[1];
    _is_island(grid, newX, newY, seen);
}

# 0-3) Tricks

# we don't need to declare y,z in func, but we can use them in the func directly
# and can get the returned value as well, this trick is being used a lot in the dfs
def test():
    def func(x):
        print ("x = " + str(x) + " y = " + str(y))
        for i in range(3):
            z.append(i)

    x = 0
    y = 100
    z = []
    func(x)
test()
print (z)

# Problems by Pattern

# Pattern-Based Problem Classification

# Pattern 1: Tree Traversal Problems

Problem	LC #	Difficulty	Key Technique	Template
Binary Tree Inorder Traversal	94	Easy	Stack/Recursion	Template 1
Binary Tree Preorder Traversal	144	Easy	Stack/Recursion	Template 1
Binary Tree Postorder Traversal	145	Easy	Stack/Recursion	Template 1
Serialize and Deserialize Binary Tree	297	Hard	DFS encoding	Template 1
Serialize and Deserialize BST	449	Medium	BST property	Template 1
Binary Tree Paths	257	Easy	Path tracking	Template 3
Same Tree	100	Easy	Simultaneous DFS	Template 1

# Pattern 2: Path Problems

Problem	LC #	Difficulty	Key Technique	Template
Path Sum	112	Easy	DFS traversal	Template 3
Path Sum II	113	Medium	Backtracking	Template 3
Binary Tree Maximum Path Sum	124	Hard	Global max	Template 6
Diameter of Binary Tree	543	Easy	Bottom-up	Template 6
Longest Univalue Path	687	Medium	Bottom-up	Template 6
Sum Root to Leaf Numbers	129	Medium	Path tracking	Template 3

# Pattern 3: Graph Traversal Problems

Problem	LC #	Difficulty	Key Technique	Template
Number of Islands	200	Medium	Grid DFS	Template 2
Max Area of Island	695	Medium	Grid DFS	Template 2
Clone Graph	133	Medium	HashMap	Template 2
Course Schedule	207	Medium	Cycle detection	Template 2
Course Schedule II	210	Medium	Topological sort	Template 2
Pacific Atlantic Water Flow	417	Medium	Multi-source	Template 2
Evaluate Division	399	Medium	Graph traversal	Template 2
Minesweeper	529	Medium	Grid exploration	Template 2

# Pattern 4: Backtracking Problems

Problem	LC #	Difficulty	Key Technique	Template
Permutations	46	Medium	Backtrack	Template 4
Subsets	78	Medium	Backtrack	Template 4
Combination Sum	39	Medium	Backtrack	Template 4
Letter Combinations	17	Medium	Backtrack	Template 4
Generate Parentheses	22	Medium	Backtrack	Template 4
Word Search	79	Medium	Grid backtrack	Template 4
N-Queens	51	Hard	Backtrack	Template 4

# Pattern 5: Tree Modification Problems

Problem	LC #	Difficulty	Key Technique	Template
Delete Node in BST	450	Medium	BST delete	Template 5
Insert into BST	701	Medium	BST insert	Template 5
Trim a Binary Search Tree	669	Medium	Conditional trim	Template 5
Convert BST to Greater Tree	538	Medium	Reverse inorder	Template 5
Invert Binary Tree	226	Easy	Tree swap	Template 5
Flatten Binary Tree	114	Medium	In-place modify	Template 5

# Pattern 6: Subtree & Aggregation Problems

Problem	LC #	Difficulty	Key Technique	Template
Most Frequent Subtree Sum	508	Medium	HashMap	Template 6
Find Duplicate Subtrees	652	Medium	Serialization	Template 6
Lowest Common Ancestor	236	Medium	Bottom-up	Template 6
Equal Tree Partition	663	Medium	Subtree sum	Template 6
Maximum Product of Splitted Tree	1339	Medium	All sums	Template 6
Validate Binary Search Tree	98	Medium	Min/Max bounds	Template 1
Split BST	776	Medium	Recursive split	Template 5

# Pattern 7: Boundary Elimination (2-Pass DFS)

Problem	LC #	Difficulty	Key Technique	Template
Number of Closed Islands	1254	Medium	Boundary flood	Template 7
Surrounded Regions	130	Medium	Border elimination	Template 7
Pacific Atlantic Water Flow	417	Medium	Two oceans	Template 7
Number of Enclaves	1020	Medium	Border-connected	Template 7

# Pattern 8: Path Signatures (Shape Encoding)

Problem	LC #	Difficulty	Key Technique	Template
Number of Distinct Islands	694	Medium	Directional encoding	Template 8
Number of Distinct Islands II	711	Hard	Handle rotations/reflections	Template 8
Find Duplicate Subtrees	652	Medium	Tree serialization	Template 8
Most Frequent Subtree Sum	508	Medium	Subtree signature	Template 8

# Pattern 9: DFS with Validation (Sub-Component Detection)

Problem	LC #	Difficulty	Key Technique	Template
Count Sub Islands	1905	Medium	Boolean flag propagation	Template 9
Number of Islands	200	Medium	Basic component counting	Template 2
Max Area of Island	695	Medium	Component size tracking	Template 2
Island Perimeter	463	Easy	Edge counting	Template 2
Making A Large Island	827	Hard	Component merging	Template 2

# Pattern 10: Bidirectional Graph with Direction Tracking

Problem	LC #	Difficulty	Key Technique	Template
Reorder Routes to Make All Paths Lead to the City Zero	1466	Medium	Bidirectional graph + direction flags	Template 10
Minimum Number of Days to Disconnect Island	1568	Hard	Graph modification (related)	-
Remove Max Number of Edges to Keep Graph Fully Traversable	1579	Hard	Edge orientation (related)	-

# Pattern 11: Component Pair Counting (Unreachable Pairs)

Problem	LC #	Difficulty	Key Technique	Template
Count Unreachable Pairs of Nodes in an Undirected Graph	2316	Medium	Component counting + cumulative multiplication	Template 11
Number of Connected Components in an Undirected Graph	323	Medium	Basic component counting	Template 2
Number of Provinces	547	Medium	Component detection	Template 2

# Complete Problem List by Difficulty

# Easy Problems (Foundation)

• LC 94: Binary Tree Inorder Traversal - Basic DFS
• LC 100: Same Tree - Parallel DFS
• LC 101: Symmetric Tree - Mirror DFS
• LC 104: Maximum Depth - Simple recursion
• LC 112: Path Sum - Path tracking
• LC 144: Binary Tree Preorder Traversal - Stack usage
• LC 145: Binary Tree Postorder Traversal - Stack manipulation
• LC 226: Invert Binary Tree - Tree modification
• LC 257: Binary Tree Paths - Path collection
• LC 543: Diameter of Binary Tree - Global max pattern
• LC 572: Subtree of Another Tree - Tree matching

# Medium Problems (Core)

• LC 98: Validate BST - Bounds checking
• LC 113: Path Sum II - Backtracking paths
• LC 130: Surrounded Regions - Boundary elimination
• LC 133: Clone Graph - HashMap + DFS
• LC 200: Number of Islands - Grid DFS
• LC 207: Course Schedule - Cycle detection
• LC 210: Course Schedule II - Topological sort
• LC 236: Lowest Common Ancestor - Bottom-up DFS
• LC 297: Serialize/Deserialize Tree - DFS encoding
• LC 399: Evaluate Division - Graph DFS
• LC 417: Pacific Atlantic Water Flow - Multi-source DFS
• LC 450: Delete Node in BST - Tree restructuring
• LC 449: Serialize/Deserialize BST - BST property
• LC 472: Concatenated Words - Word break DFS
• LC 508: Most Frequent Subtree Sum - Aggregation
• LC 529: Minesweeper - Grid exploration
• LC 538: Convert BST to Greater Tree - Reverse inorder
• LC 652: Find Duplicate Subtrees - Serialization
• LC 663: Equal Tree Partition - Subtree sums
• LC 669: Trim BST - Conditional modification
• LC 695: Max Area of Island - Connected component
• LC 701: Insert into BST - BST insertion
• LC 1466: Reorder Routes to Make All Paths Lead to the City Zero - Bidirectional graph with direction tracking
• LC 1905: Count Sub Islands - DFS with validation
• LC 2316: Count Unreachable Pairs of Nodes in an Undirected Graph - Component pair counting
• LC 737: Sentence Similarity II - Graph connectivity
• LC 776: Split BST - Advanced manipulation
• LC 1020: Number of Enclaves - Boundary elimination
• LC 1254: Number of Closed Islands - 2-Pass DFS
• LC 1339: Maximum Product of Splitted Tree - All subtree sums

# Hard Problems (Advanced)

• LC 124: Binary Tree Maximum Path Sum - Global optimization
• LC 297: Serialize and Deserialize Binary Tree - Complex encoding
• LC 51: N-Queens - Complex backtracking
• LC 329: Longest Increasing Path in Matrix - Memoized DFS
• LC 3319: K-th Largest Perfect Subtree - Complex aggregation

# 1-1) Basic OP

# 1-1-1) Add 1 to all node.value in Binary tree?

# Example) Add 1 to all node.value in Binary tree?
def dfs(root):
    if not root:
        return 
    root.val += 1 
    dfs(root.left)
    dfs(root.right)

# 1-1-2) check if 2 Binary tree are the same

# Example) check if 2 Binary tree are the same ? 
def dfs(root1, root2):
    if root1 == root2 == None:
        return True 
    if root1 is not None and root2 is None:
        return False 
    if root1 is None and root2 is not None:
        return False 
    else:
        if root1.val != root2.value:
            return False 
    return dfs(root1.left, root2.left) \
           and dfs(root1.right, root2.right)

# 1-1-3) check if a value exist in the BST

# Example) check if a value exist in the BST
def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    return dfs(root.left, value) or dfs(root.right, value)

# optimized : BST prpoerty :  root.right > root.val > root.left
def dfs(root, value):
    if not root:
        return False
    if root.val == value:
        return True
    if root.val > value:
        return dfs(root.left, value) 
    if root.val < value:
        return dfs(root.right, value)

# 1-1-4) get sum of sub tree

# get sum of sub tree
# LC 508 Most Frequent Subtree Sum
def get_sum(root):
    if not root:
        return 0
    ### NOTE THIS !!!
    #  -> we need to do get_sum(root.left), get_sum(root.right) on the same time
    s = get_sum(root.left) + root.val + get_sum(root.right)
    res.append(s)
    return s

# 1-1-5) get aggregated sum for every node in tree

# LC 663 Equal Tree Partition
# LC 508 Most Frequent Subtree Sum
seen = []
def _sum(root):
    if not root:
        return 0
    seen.append( root.val + _sum(root.left) + _sum(root.right) )

# 1-1-6) Convert BST to Greater Tree

# Convert BST to Greater Tree 
# LC 538
_sum = 0
def dfs(root):
    dfs(root.right)
    _sum += root.val
    root.val = _sum
    dfs(root.left)

# 1-1-7) Serialize and Deserialize Binary Tree

# LC 297. Serialize and Deserialize Binary Tree
# please check below 2) LC Example
# V0
# IDRA : DFS
class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string
        
        return rserialize(root, '')    

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None
                
            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

        data_list = data.split(',')
        root = rdeserialize(data_list)
        return root

// java
// LC 297
public class Codec{
    public String serialize(TreeNode root) {

        /** NOTE !!!
         *
         *     if root == null, return "#"
         */
        if (root == null){
            return "#";
        }

        /** NOTE !!! return result via pre-order, split with "," */
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public TreeNode deserialize(String data) {

        /** NOTE !!!
         *
         *   1) init queue and append serialize output
         *   2) even use queue, but helper func still using DFS
         */
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return helper(queue);
    }

    private TreeNode helper(Queue<String> queue) {

        // get val from queue first
        String s = queue.poll();

        if (s.equals("#")){
            return null;
        }
        /** NOTE !!! init current node  */
        TreeNode root = new TreeNode(Integer.valueOf(s));
        /** NOTE !!!
         *
         *    since serialize is "pre-order",
         *    deserialize we use "pre-order" as well
         *    e.g. root -> left sub tree -> right sub tree
         *    -> so we get sub tree via below :
         *
         *       root.left = helper(queue);
         *       root.right = helper(queue);
         *
         */
        root.left = helper(queue);
        root.right = helper(queue);
        /** NOTE !!! don't forget to return final deserialize result  */
        return root;
    }
}

# 1-1-8) Serialize and Deserialize BST

# LC 449. Serialize and Deserialize BST
# please check below 2) LC Example
# NOTE : there is also a bfs approach
# V1'
# IDEA : BST property
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/212043/Python-solution
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def dfs(root):
            if not root:
                return 
            res.append(str(root.val) + ",")
            dfs(root.left)
            dfs(root.right)
            
        res = []
        dfs(root)
        return "".join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        lst = data.split(",")
        lst.pop()
        stack = []
        head = None
        for n in lst:
            n = int(n)
            if not head:
                head = TreeNode(n)
                stack.append(head)
            else:
                node = TreeNode(n)
                if n < stack[-1].val:
                    stack[-1].left = node
                else:
                    while stack and stack[-1].val < n: 
                        u = stack.pop()
                    u.right = node
                stack.append(node)
        return head

# 1-1-9) find longest distance between nodes

// java
// LC 543 Diameter of Binary Tree
// V1
// IDEA : DFS
// https://leetcode.com/problems/diameter-of-binary-tree/editorial/

int diameter;

public int diameterOfBinaryTree_2(TreeNode root) {
    diameter = 0;
    longestPath(root);
    return diameter;
}
private int longestPath(TreeNode node){
    if(node == null) return 0;
    // recursively find the longest path in
    // both left child and right child
    int leftPath = longestPath(node.left);
    int rightPath = longestPath(node.right);

    // update the diameter if left_path plus right_path is larger
    diameter = Math.max(diameter, leftPath + rightPath);

    // return the longest one between left_path and right_path;
    // remember to add 1 for the path connecting the node and its parent
    return Math.max(leftPath, rightPath) + 1;
}

# 1-1-10) Compare node val with path

// java
// LC 1448

private void dfsCheckGoodNode(TreeNode node, int maxSoFar) {
    if (node == null)
        return;

    // Check if the current node is good
    if (node.val >= maxSoFar) {
        res++;
        maxSoFar = node.val; // Update max value seen so far
    }

    // Recur for left and right children
    dfsCheckGoodNode(node.left, maxSoFar);
    dfsCheckGoodNode(node.right, maxSoFar);
}

# 2) LC Example

# 2-1) Validate Binary Search Tree

# 098 Validate Binary Search Tree
### NOTE : there is also bfs solution
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Recursion/validate-binary-search-tree.py
class Solution(object):
    def isValidBST(self, root):
        return self.valid(root, float('-inf'), float('inf'))
        
    def valid(self, root, min_, max_):
        if not root: return True
        if root.val >= max_ or root.val <= min_:
            return False
        return self.valid(root.left, min_, root.val) and self.valid(root.right, root.val, max_)

# 2-2) Insert into a Binary Search Tree

// java
// LC 701

public TreeNode insertIntoBST_0_1(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }

    /** 
     *  NOTE !!! 
     *  
     *   via below, we can still `MODIFY root value`,
     *   even it's not declared as a global variable
     *   
     *   -> e.g. we have root as input,
     *      within `insertNodeHelper` method,
     *      we append `new sub tree` to root as its left, right sub tree
     *
     */
    insertNodeHelper(root, val); // helper modifies the tree in-place
    return root;
}

public void insertNodeHelper(TreeNode root, int val) {
    if (val < root.val) {
        if (root.left == null) {
            root.left = new TreeNode(val);
        } else {
            /** NOTE !!!
             * 
             *  no need to return val,
             *  since we `append sub tree` to root directly
             *  in the method (e.g. root.left == ..., root.right = ...)
             */
            insertNodeHelper(root.left, val);
        }
    } else {
        if (root.right == null) {
            root.right = new TreeNode(val);
        } else {
            insertNodeHelper(root.right, val);
        }
    }
}

# 701 Insert into a Binary Search Tree

# VO : recursion + dfs
class Solution(object):
    def insertIntoBST(self, root, val):
        if not root: 
            return TreeNode(val)
        if root.val < val: 
            root.right = self.insertIntoBST(root.right, val);
        elif root.val > val: 
            root.left = self.insertIntoBST(root.left, val);
        return(root)

`

# 2-3) Delete Node in a BST

# 450 Delete Node in a BST
# V0
# IDEA : RECURSION + BST PROPERTY
#### 2 CASES :
#   -> CASE 1 : root.val == key and NO right subtree 
#                -> swap root and root.left, return root.left
#   -> CASE 2 : root.val == key and THERE IS right subtree
#                -> 1) go to 1st RIGHT sub tree
#                -> 2) iterate to deepest LEFT subtree
#                -> 3) swap root and  `deepest LEFT subtree` then return root
class Solution(object):
    def deleteNode(self, root, key):
        if not root: return None
        if root.val == key:
            # case 1 : NO right subtree 
            if not root.right:
                left = root.left
                return left
            # case 2 : THERE IS right subtree
            else:
                ### NOTE : find min in "right" sub-tree
                #           -> because BST property, we ONLY go to 1st right tree (make sure we find the min of right sub-tree)
                #           -> then go to deepest left sub-tree
                right = root.right
                while right.left:
                    right = right.left
                ### NOTE : we need to swap root, right ON THE SAME TIME
                root.val, right.val = right.val, root.val
        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)
        return root

// java
// LC 450
// V0
// IDEA: DFS + BST property
/**
 *
 * (when found a node to delete)
 *
 *    // Case 1: No children
 *
 *    // Case 2: One child
 *
 *    // Case 3: Two children
 *
 */
/**
 *
 *  Summary of Deletion Strategy:
 *
 *
 *  | Case         | Description        | What Happens                                  |
 * |--------------|--------------------|-----------------------------------------------|
 * | Leaf         | No children         | Return `null`                                 |
 * | One Child    | One child           | Replace node with its child                   |
 * | Two Children | Both children       | Replace with in-order successor, then delete the successor |
 *
 *
 *  `in-order successor`:  Left → root → Right
 */

public TreeNode deleteNode(TreeNode root, int key) {
    return deleteNodeHelper_0(root, key);
}

private TreeNode deleteNodeHelper_0(TreeNode root, int key) {
    if (root == null) {
        return null;
    }

    /**
     * CASE 1)  NOT found a node to delete
     */
    if (key < root.val) {
        // search in left subtree
        /**
         *  NOTE !!!
         *
         *   we assign `left sub tree` as res from deleteNodeHelper_0(root.left, key)
         *
         *   -> NOT return `deleteNodeHelper_0(root.left, key)`
         *      as res directly, since it deleteNodeHelper_0
         *      could NOT be a null val, we need it to assign root.left,
         *      so we can keep `whole BST info`
         */
        root.left = deleteNodeHelper_0(root.left, key);
    } else if (key > root.val) {
        // search in right subtree
        /**
         *  NOTE !!!
         *
         *   we assign `right sub tree` as res from deleteNodeHelper_0(root.right, key)
         */
        root.right = deleteNodeHelper_0(root.right, key);
    }
    /**
     * CASE 2)  Found a node to delete
     */
    else {
        // Case 1: No left child
        if (root.left == null) {
            return root.right;
        }

        // Case 2: No right child
        if (root.right == null) {
            return root.left;
        }

        /**
         *  NOTE !!!! below
         *
         *  step 1) find `min` val  (`sub right tree`)
         *  step 2) set root val as min val
         *  step 3)  delete the `min` val node from sub right tree
         *             - `recursively` call `deleteNodeHelper`
         *
         */
        // Case 3: Two children → find inorder successor
        /**
         *  NOTE !!!
         *
         *   we need to find a `min` tree from `sub right tree`
         *   as a node to `swap` with current node.
         *
         *   Reason:
         *      since it is a BST, so  `left < root < right`.
         *      so after swapping `min` from sub right tree.
         *      with current node
         *          -> the tree `remains` BST.
         *          we DON'T have to do any further modification.
         *
         */
        TreeNode minNode = findMin_0(root.right);
        root.val = minNode.val; // copy value
        root.right = deleteNodeHelper(root.right, minNode.val); // delete successor
    }

    return root;
}

private TreeNode findMin_0(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

# 2-4) Find Duplicate Subtrees

# 652 Find Duplicate Subtrees
import collections
class Solution(object):
    def findDuplicateSubtrees(self, root):
        res = []
        m = collections.defaultdict(int)
        self.dfs(root, m, res)
        return res

    def dfs(self, root, m, res):
        if not root:
            return '#'
        path = str(root.val) + '-' + self.dfs(root.left, m, res) + '-' + self.dfs(root.right, m, res)
        if m[path] == 1:
            res.append(root) 
        m[path] += 1
        return path

# 2-5) Trim a BST

# 669 Trim a Binary Search Tree
class Solution:
    def trimBST(self, root, L, R):
        if not root:
            return None
        if root.val > R:
            return self.trimBST(root.left, L, R)
        elif root.val < L:
            return self.trimBST(root.right, L, R)
        else:
            root.left = self.trimBST(root.left, L, R)
            root.right = self.trimBST(root.right, L, R)
            return root

# 2-6) Maximum Width of Binary Tree

# 662 Maximum Width of Binary Tree
class Solution(object):
    def widthOfBinaryTree(self, root):
        self.ans = 0
        left = {}
        def dfs(node, depth = 0, pos = 0):
            if node:
                left.setdefault(depth, pos)
                self.ans = max(self.ans, pos - left[depth] + 1)
                dfs(node.left, depth + 1, pos * 2)
                dfs(node.right, depth + 1, pos * 2 + 1)

        dfs(root)
        return self.ans

# 2-7) Equal Tree Partition

# 663 Equal Tree Partition
# V0
# IDEA : DFS + cache
class Solution(object):
    def checkEqualTree(self, root):
        seen = []

        def sum_(node):
            if not node: return 0
            seen.append(sum_(node.left) + sum_(node.right) + node.val)
            return seen[-1]

        sum_(root)
        #print ("seen = " + str(seen))
        return seen[-1] / 2.0 in seen[:-1]

# V0'
class Solution(object):
    def checkEqualTree(self, root):
        seen = []

        def sum_(node):
            if not node: return 0
            seen.append(sum_(node.left) + sum_(node.right) + node.val)
            return seen[-1]
            
        total = sum_(root)
        seen.pop()
        return total / 2.0 in seen

# 2-8) Split BST

# 776 Split BST
# V0
# IDEA : BST properties (left < root < right) + recursion
# https://blog.csdn.net/magicbean2/article/details/79679927
# https://www.itdaan.com/tw/d58594b92742689b5769f9827365e8b4
### STEPS
#  -> 1) check whether root.val > or < V
#     -> if root.val > V : 
#           - NO NEED TO MODIFY ALL RIGHT SUB TREE
#           - BUT NEED TO re-connect nodes in LEFT SUB TREE WHICH IS BIGGER THAN V (root.left = right)
#     -> if root.val < V : 
#           - NO NEED TO MODIFY ALL LEFT SUB TREE
#           - BUT NEED TO re-connect nodes in RIGHT SUB TREE WHICH IS SMALLER THAN V (root.right = left)
# -> 2) return result
class Solution(object):
    def splitBST(self, root, V):
        if not root: return [None, None]
        ### NOTE : if root.val <= V
        if root.val > V:
            left, right = self.splitBST(root.left, V)
            root.left = right
            return [left, root]
        ### NOTE : if root.val > V
        else:
            left, right = self.splitBST(root.right, V)
            root.right = left
            return [root, right]

# 2-9) Evaluate Division

# 399 Evaluate Division
# there is also an "union find" solution
class Solution:
    def calcEquation(self, equations, values, queries):
        from collections import defaultdict
        # build graph
        graph = defaultdict(dict)
        for (x, y), v in zip(equations, values):
            graph[x][y] = v
            graph[y][x] = 1.0/v
        ans = [self.dfs(x, y, graph, set()) for (x, y) in queries]
        return ans

    def dfs(self, x, y, graph, visited):
        if not graph:
            return
        if x not in graph or y not in graph:
            return -1
        if x == y:
            return 1
        visited.add(x)
        for n in graph[x]:
            if n in visited:
                continue
            visited.add(n)
            d = self.dfs(n, y, graph, visited)
            if d > 0:
                return d * graph[x][n]
        return -1.0

// java
// V1
// IDEA: DFS
// https://leetcode.com/problems/evaluate-division/solutions/3543256/image-explanation-easiest-concise-comple-okpu/
public double[] calcEquation_1(List<List<String>> equations, double[] values, List<List<String>> queries) {
    HashMap<String, HashMap<String, Double>> gr = buildGraph(equations, values);
    double[] finalAns = new double[queries.size()];

    for (int i = 0; i < queries.size(); i++) {
        String dividend = queries.get(i).get(0);
        String divisor = queries.get(i).get(1);

        /** NOTE !!!
         *
         *  either dividend nor divisor NOT in graph, return -1.0 directly
         */
        if (!gr.containsKey(dividend) || !gr.containsKey(divisor)) {
            finalAns[i] = -1.0;
        } else {

            /** NOTE !!!
             *
             *  we use `vis` to check if element already visited
             *  (to avoid repeat accessing)
             *  `vis` init again in every loop
             */

            HashSet<String> vis = new HashSet<>();
            /**
             *  NOTE !!!
             *
             *   we init `ans` and pass it to dfs method
             *   (but dfs method return NOTHING)
             *   -> `ans` is init, and pass into dfs,
             *   -> so `ans` value is updated during dfs recursion run
             *   -> and after dfs run completed, we get the result `ans` value
             */
            double[] ans = { -1.0 };
            double temp = 1.0;
            dfs(dividend, divisor, gr, vis, ans, temp);
            finalAns[i] = ans[0];
        }
    }

    return finalAns;
}

/** NOTE !!! below dfs method */
public void dfs(String node, String dest, HashMap<String, HashMap<String, Double>> gr, HashSet<String> vis,
                double[] ans, double temp) {

    /** NOTE !!! we use `vis` to check if element already visited */
    if (vis.contains(node))
        return;

    vis.add(node);
    if (node.equals(dest)) {
        ans[0] = temp;
        return;
    }

    for (Map.Entry<String, Double> entry : gr.get(node).entrySet()) {
        String ne = entry.getKey();
        double val = entry.getValue();
        /** NOTE !!! update temp as `temp * val` */
        dfs(ne, dest, gr, vis, ans, temp * val);
    }
}

public HashMap<String, HashMap<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    HashMap<String, HashMap<String, Double>> gr = new HashMap<>();

    for (int i = 0; i < equations.size(); i++) {
        String dividend = equations.get(i).get(0);
        String divisor = equations.get(i).get(1);
        double value = values[i];

        gr.putIfAbsent(dividend, new HashMap<>());
        gr.putIfAbsent(divisor, new HashMap<>());

        gr.get(dividend).put(divisor, value);
        gr.get(divisor).put(dividend, 1.0 / value);
    }

    return gr;
}

# 2-10) Most Frequent Subtree Sum

# LC 508 Most Frequent Subtree Sum
# V0
# IDEA : DFS + TREE
class Solution(object):
    def findFrequentTreeSum(self, root):
        """
        ### NOTE : this trick : get sum of sub tree
        # LC 663 Equal Tree Partition
        """
        def get_sum(root):
            if not root:
                return 0
            s = get_sum(root.left) + root.val + get_sum(root.right)
            res.append(s)
            return s

        if not root:
            return []
        res = []
        get_sum(root)
        counts = collections.Counter(res)
        _max = max(counts.values())
        return [x for x in counts if counts[x] == _max]

# V0'
# IDEA : DFS + COUNTER
from collections import Counter
class Solution(object):
    def findFrequentTreeSum(self, root):
        def helper(root, d):
            if not root:
                return 0
            left = helper(root.left, d)
            right = helper(root.right, d)
            subtreeSum = left + right + root.val
            d[subtreeSum] = d.get(subtreeSum, 0) + 1
            return subtreeSum      
        d = {}
        helper(root, d)
        mostFreq = 0
        ans = []
        print ("d = " + str(d))
        _max_cnt = max(d.values())
        ans = []
        return [x for x in d if d[x] == _max_cnt]

# 2-11) Convert BST to Greater Tree

# LC 538 Convert BST to Greater Tree
# V0
# IDEA : DFS + recursion
#      -> NOTE : via DFS, the op will being executed in `INVERSE` order (last visit will be run first, then previous, then ...)
#      -> e.g. node1 -> node2 -> ... nodeN
#      ->      will run nodeN -> nodeN-1 ... node1
class Solution(object):

    def convertBST(self, root):
        self.sum = 0
        self.dfs(root)
        return root

    def dfs(self, node):
        if not node: 
            return
        #print ("node.val = " + str(node.val))
        self.dfs(node.right)
        self.sum += node.val
        node.val = self.sum
        self.dfs(node.left)

# V0'
# NOTE : the implementation difference on cur VS self.cur
# 1) if cur : we need to ssign output of help() func to cur
# 2) if self.cur : no need to assign, plz check V0 as reference
class Solution(object):
    def convertBST(self, root):
        def help(cur, root):
            if not root:
                ### NOTE : if not root, still need to return cur
                return cur
            ### NOTE : need to assign output of help() func to cur
            cur = help(cur, root.right)
            cur += root.val
            root.val = cur
            ### NOTE : need to assign output of help() func to cur
            cur = help(cur, root.left)
            ### NOTE : need to return cur
            return cur

        if not root:
            return

        cur = 0
        help(cur, root)
        return root

# 2-12) Number of Islands

# LC 200 Number of Islands, check LC 694, 711 as well
# V0 
# IDEA : DFS
class Solution(object):
    def numIslands(self, grid):
        def dfs(grid, item):
            if grid[item[0]][item[1]] == "0":
                return

            ### NOTE : MAKE grid[item[0]][item[1]] = 0 -> avoid visit again
            grid[item[0]][item[1]] = 0
            moves = [(0,1),(0,-1),(1,0),(-1,0)]
            for move in moves:
                _x = item[0] + move[0]
                _y = item[1] + move[1]
                ### NOTE : the boundary
                #       -> _x < l, _y < w
                if 0 <= _x < l and 0 <= _y < w and grid[_x][_y] != 0:
                    dfs(grid, [_x, _y])
  
        if not grid:
            return 0
        res = 0
        l = len(grid)
        w = len(grid[0])
        for i in range(l):
            for j in range(w):
                if grid[i][j] == "1":
                    ### NOTE : we go through every "1" in grids, and run dfs once
                    #         -> once dfs completed, we make res += 1 in each iteration
                    dfs(grid, [i,j])
                    res += 1
        return res

# 2-13) Max Area of Island

# LC 695. Max Area of Island
# V1
# https://blog.csdn.net/fuxuemingzhu/article/details/79182435
# IDEA : DFS 
# * PLEASE NOTE THAT IT IS NEEDED TO GO THROUGH EVERY ELEMENT IN THE GRID 
#   AND RUN THE DFS WITH IN THIS PROBLEM
class Solution(object):
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.res = 0
        self.island = 0
        M, N = len(grid), len(grid[0])
        for i in range(M):
            for j in range(N):
                if grid[i][j]:
                    self.dfs(grid, i, j)
                    self.res = max(self.res, self.island)
                    self.island = 0
        return self.res
    
    def dfs(self, grid, i, j): # ensure grid[i][j] == 1
        M, N = len(grid), len(grid[0])
        grid[i][j] = 0
        self.island += 1
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        for d in dirs:
            x, y = i + d[0], j + d[1]
            if 0 <= x < M and 0 <= y < N and grid[x][y]:
                self.dfs(grid, x, y)

# 2-14) Binary Tree Paths

# LC 257. Binary Tree Paths
# V0 
# IDEA : DFS 
class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        res, path_list = [], []
        self.dfs(root, path_list, res)
        return res

    def dfs(self, root, path_list, res):
        if not root:
            return
        path_list.append(str(root.val))
        if not root.left and not root.right:
            res.append('->'.join(path_list))
        if root.left:
            self.dfs(root.left, path_list, res)
        if root.right:
            self.dfs(root.right, path_list, res)
        path_list.pop()

# 2-15) Lowest Common Ancestor of a Binary Tree

# LC 236 Lowest Common Ancestor of a Binary Tree
# V0
# IDEA : RECURSION + POST ORDER TRANSVERSAL
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):

        ### NOTE here
        # if not root or find p in tree or find q in tree
        # -> then we quit the recursion and return root

        ### NOTE : we compare `p == root` and  `q == root`
        if not root or p == root or q == root:
            return root
        ### NOTE here
        #  -> not root.left, root.right, BUT left, right
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        ### NOTE here
        # find q and p on the same time -> LCA is the current node (root)
        # if left and right -> p, q MUST in left, right sub tree respectively

        ### NOTE : if left and right, means this root is OK for next recursive
        if left and right:
            return root
        ### NOTE here
        # if p, q both in left sub tree or both in right sub tree
        return left if left else right

# 2-16) Path Sum

# LC 112 Path Sum
# V0
# IDEA : DFS 
class Solution(object):
    def hasPathSum(self, root, sum):
        if not root:
            return False
        if not root.left and not root.right:
            return True if sum == root.val else False
        else:
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

# 2-17) Path Sum II

# LC 113 Path Sum II
# V0
# IDEA : DFS
class Solution(object):
    def pathSum(self, root, sum):
        if not root: return []
        res = []
        self.dfs(root, sum, res, [root.val])
        return res

    def dfs(self, root, target, res, path):
        if not root: return
        if sum(path) == target and not root.left and not root.right:
            res.append(path)
            return
        if root.left:
            self.dfs(root.left, target, res, path + [root.left.val])
        if root.right:
            self.dfs(root.right, target, res, path + [root.right.val])

// java
// LC 113
// V0
// IDEA : DFS + backtracking
// NOTE !!! we have res attr, so can use this.res collect result
private List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

    if (root == null){
        return this.res;
    }

    List<Integer> cur = new ArrayList<>();
    getPath(root, cur, targetSum);
    return this.res;
}

 private void getPath(TreeNode root, List<Integer> cur, int targetSum){

    // return directly if root is null (not possible to go further, so just quit directly)
    if (root == null){
        return;
    }

    // NOTE !!! we add val to cache here instead of while calling method recursively ( e.g. getPath(root.left, cur, targetSum - root.val))
    //          -> so we just need to backtrack (cancel last operation) once (e.g. cur.remove(cur.size() - 1);)
    //          -> please check V0' for example with backtrack in recursively step
    cur.add(root.val);

    if (root.left == null && root.right == null && targetSum == root.val){
        this.res.add(new ArrayList<>(cur));
    }else{
        // NOTE !!! we update targetSum here (e.g. targetSum - root.val)
        getPath(root.left, cur, targetSum - root.val);
        getPath(root.right, cur, targetSum - root.val);
    }

     // NOTE !!! we do backtrack here (cancel previous adding to cur)
     cur.remove(cur.size() - 1);
}

# 2-7) Clone graph

# 133 Clone graph
# note : there is also a BFS solution
# V0
# IDEA : DFS
# NOTE :
#  -> 1) we init node via : node_copy = Node(node.val, [])
#  -> 2) we copy graph via dict
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        node_copy = self.dfs(node, dict())
        return node_copy
    
    def dfs(self, node, hashd):
        if not node: return None
        if node in hashd: return hashd[node]
        node_copy = Node(node.val, [])
        hashd[node] = node_copy
        for n in node.neighbors:
            n_copy = self.dfs(n, hashd)
            if n_copy:
                node_copy.neighbors.append(n_copy)
        return node_copy

# 2-8) Sentence Similarity II

# LC 737. Sentence Similarity II
# NOTE : there is also union-find solution
# V0
# IDEA : DFS
from collections import defaultdict
class Solution(object):
    def areSentencesSimilarTwo(self, sentence1, sentence2, similarPairs):
        # helper func
        def dfs(w1, w2, visited):
            for j in d[w2]:
                if w1 == w2:
                    return True
                elif j not in visited:
                    visited.add(j)
                    if dfs(w1, j, visited):
                        return True
            return False
        
        # edge case
        if len(sentence1) != len(sentence2):
            return False
      
        d = defaultdict(list)
        for a, b in similarPairs:
            d[a].append(b)
            d[b].append(a)
            
        for i in range(len(sentence1)):
            visited =  set([sentence2[i]])
            if sentence1[i] != sentence2[i] and not dfs(sentence1[i],  sentence2[i], visited):
                return False
        return True

# 2-9) Concatenated Words

# LC 472. Concatenated Words
# V1
# http://bookshadow.com/weblog/2016/12/18/leetcode-concatenated-words/
# IDEA : DFS 
class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        ans = []
        self.wordSet = set(words)
        for word in words:
            self.wordSet.remove(word) # avoid the search process find itself (word) when search all word in words  
            if self.search(word):
                ans.append(word)
            self.wordSet.add(word)    # add the word back for next search with new "word"
        return ans

    def search(self, word):
        if word in self.wordSet:
            return True
        for idx in range(1, len(word)):
            if word[:idx] in self.wordSet and self.search(word[idx:]):
                return True
        return False

# 2-10) Maximum Product of Splitted Binary Tree

# LC 1339. Maximum Product of Splitted Binary Tree
# V0
# IDEA : DFS
class Solution(object):
    def maxProduct(self, root):
        all_sums = []

        def tree_sum(subroot):
            if subroot is None: return 0
            left_sum = tree_sum(subroot.left)
            right_sum = tree_sum(subroot.right)
            total_sum = left_sum + right_sum + subroot.val
            all_sums.append(total_sum)
            return total_sum

        total = tree_sum(root)
        best = 0
        for s in all_sums:
            best = max(best, s * (total - s))   
        return best % (10 ** 9 + 7)

# 2-11) Serialize and Deserialize Binary Tree

# LC 297. Serialize and Deserialize Binary Tree
# V0
# IDRA : DFS
class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string
        
        return rserialize(root, '')    

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None
                
            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

        data_list = data.split(',')
        root = rdeserialize(data_list)
        return root

# V1
# IDEA : same as LC 297
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93283/Python-solution-using-BST-property
class Codec:

    def serialize(self, root):
        vals = []
        self._preorder(root, vals)
        return ','.join(vals)
        
    def _preorder(self, node, vals):
        if node:
            vals.append(str(node.val))
            self._preorder(node.left, vals)
            self._preorder(node.right, vals)
        
    def deserialize(self, data):
        vals = collections.deque(map(int, data.split(','))) if data else []
        return self._build(vals, -float('inf'), float('inf'))

    def _build(self, vals, minVal, maxVal):
        if vals and minVal < vals[0] < maxVal:
            val = vals.popleft()
            root = TreeNode(val)
            root.left = self._build(vals, minVal, val)
            root.right = self._build(vals, val, maxVal)
            return root
        else:
            return None

# 2-12) Serialize and Deserialize BST

# LC 449. Serialize and Deserialize BST
# V0
# IDEA : BFS + queue op
class Codec:
    def serialize(self, root):
        if not root:
            return '{}'

        res = [root.val]
        q = [root]

        while q:
            new_q = []
            for i in range(len(q)):
                tmp = q.pop(0)
                if tmp.left:
                    q.append(tmp.left)
                    res.extend( [tmp.left.val] )
                else:
                    res.append('#')
                if tmp.right:
                    q.append(tmp.right)
                    res.extend( [tmp.right.val] )
                else:
                    res.append('#')

        while res and res[-1] == '#':
                    res.pop()

        return '{' + ','.join(map(str, res)) + '}' 


    def deserialize(self, data):
        if data == '{}':
            return

        nodes = [ TreeNode(x) for x in data[1:-1].split(",") ]
        root = nodes.pop(0)
        p = [root]
        while p:
            new_p = []
            for n in p:
                if nodes:
                    left_node = nodes.pop(0)
                    if left_node.val != '#':
                        n.left = left_node
                        new_p.append(n.left)
                    else:
                        n.left = None
                if nodes:
                    right_node = nodes.pop(0)
                    if right_node.val != '#':
                        n.right = right_node
                        new_p.append(n.right)
                    else:
                        n.right = None
            p = new_p 
             
        return root

# V1
# IDEA : same as LC 297
# https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93283/Python-solution-using-BST-property
class Codec:

    def serialize(self, root):
        vals = []
        self._preorder(root, vals)
        return ','.join(vals)
        
    def _preorder(self, node, vals):
        if node:
            vals.append(str(node.val))
            self._preorder(node.left, vals)
            self._preorder(node.right, vals)
        
    def deserialize(self, data):
        vals = collections.deque(map(int, data.split(','))) if data else []
        return self._build(vals, -float('inf'), float('inf'))

    def _build(self, vals, minVal, maxVal):
        if vals and minVal < vals[0] < maxVal:
            val = vals.popleft()
            root = TreeNode(val)
            root.left = self._build(vals, minVal, val)
            root.right = self._build(vals, val, maxVal)
            return root
        else:
            return None

# 2-12) Number of Closed Islands (2-Pass DFS)

// java
// LC 1254
// V0
// IDEA: 2-Pass DFS (Boundary Elimination)
/**
 * Algorithm:
 * Pass 1: Start from all boundary cells and flood-fill to eliminate
 *         all islands connected to the boundary (these cannot be closed)
 * Pass 2: Count remaining land cells as closed islands
 *
 * Time: O(m×n), Space: O(m×n) for recursion stack
 */
public int closedIsland(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }

    int rows = grid.length;
    int cols = grid[0].length;

    // Pass 1: Eliminate boundary-connected islands
    // Flood top and bottom borders
    for (int c = 0; c < cols; c++) {
        flood(grid, 0, c);           // Top border
        flood(grid, rows - 1, c);    // Bottom border
    }

    // Flood left and right borders
    for (int r = 0; r < rows; r++) {
        flood(grid, r, 0);           // Left border
        flood(grid, r, cols - 1);    // Right border
    }

    // Pass 2: Count closed islands
    int count = 0;
    for (int r = 1; r < rows - 1; r++) {
        for (int c = 1; c < cols - 1; c++) {
            if (grid[r][c] == 0) {
                count++;
                flood(grid, r, c);  // Mark entire island
            }
        }
    }

    return count;
}

private void flood(int[][] grid, int r, int c) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base case: out of bounds or water
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
        return;
    }

    grid[r][c] = 1;  // Mark land as water (visited)

    // Flood 4-directionally
    flood(grid, r + 1, c);
    flood(grid, r - 1, c);
    flood(grid, r, c + 1);
    flood(grid, r, c - 1);
}

# python
# LC 1254
def closedIsland(grid):
    """
    2-Pass DFS approach
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def flood(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1:
            return
        grid[r][c] = 1
        flood(r + 1, c)
        flood(r - 1, c)
        flood(r, c + 1)
        flood(r, c - 1)

    # Pass 1: Eliminate boundary islands
    for c in range(cols):
        flood(0, c)
        flood(rows - 1, c)

    for r in range(rows):
        flood(r, 0)
        flood(r, cols - 1)

    # Pass 2: Count closed islands
    count = 0
    for r in range(1, rows - 1):
        for c in range(1, cols - 1):
            if grid[r][c] == 0:
                count += 1
                flood(r, c)

    return count

# 2-13) Pacific Atlantic Water Flow

// java
// LC 417
// V0
// IDEA : DFS (fixed by GPT)

public List<List<Integer>> pacificAtlantic(int[][] heights) {

    if (heights == null || heights.length == 0 || heights[0].length == 0) {
        return new ArrayList<>();
    }

    int l = heights.length;
    int w = heights[0].length;

    /**
     *
     * The pacificReachable and atlanticReachable arrays are used to keep track
     * of which cells in the matrix can reach the Pacific and Atlantic oceans, respectively.
     *
     *
     * - pacificReachable[i][j] will be true if water
     *   can flow from cell (i, j) to the Pacific Ocean.
     *   The Pacific Ocean is on the top and left edges of the matrix.
     *
     * - atlanticReachable[i][j] will be true if water
     *   can flow from cell (i, j) to the Atlantic Ocean.
     *   The Atlantic Ocean is on the bottom and right edges of the matrix.
     *
     *
     * NOTE !!!!
     *
     * The pacificReachable and atlanticReachable arrays serve a dual purpose:
     *
     * Tracking Reachability: They track whether each cell can reach the respective ocean.
     *
     * Tracking Visited Cells: They also help in tracking whether a cell has already
     *                         been visited during the depth-first search (DFS)
     *                         to prevent redundant work and infinite loops.
     *
     *
     *   NOTE !!!
     *
     *    we use `boolean[][]` to track if a cell is reachable
     */
    boolean[][] pacificReachable = new boolean[l][w];
    boolean[][] atlanticReachable = new boolean[l][w];

    // check on x-axis
    /**
     *  NOTE !!!
     *
     *   we loop EVERY `cell` at x-axis  ( (x_1, 0), (x_2, 0), .... (x_1, l - 1), (x_2, l - 1) ... )
     *
     */
    for (int x = 0; x < w; x++) {
        dfs(heights, pacificReachable, 0, x);
        dfs(heights, atlanticReachable, l - 1, x);
    }

    // check on y-axis
    /**
     *  NOTE !!!
     *
     *   we loop EVERY `cell` at y-axis  (  (0, y_1), (0, y_2), .... (w-1, y_1), (w-1, y_2), ... )
     *
     */
    for (int y = 0; y < l; y++) {
        dfs(heights, pacificReachable, y, 0);
        dfs(heights, atlanticReachable, y, w - 1);
    }

    List<List<Integer>> commonCells = new ArrayList<>();
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < w; j++) {
            if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                commonCells.add(Arrays.asList(i, j));
            }
        }
    }
    return commonCells;
}

/**
 *  NOTE !!!
 *
 *   this dfs func return NOTHING,
 *   e.g. it updates the matrix value `in place`
 *
 *   example:  we pass `pacificReachable` as param to dfs,
 *             it modifies values in pacificReachable in place,
 *             but NOT return pacificReachable as response
 */
private void dfs(int[][] heights, boolean[][] reachable, int y, int x) {

    int l = heights.length;
    int w = heights[0].length;

    reachable[y][x] = true;

    int[][] directions = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    for (int[] dir : directions) {
        int newY = y + dir[0];
        int newX = x + dir[1];

        /**
         *  NOTE !!!  only meet below conditions, then do recursion call
         *
         *  1. newX, newY still in range
         *  2. newX, newY is still not reachable (!reachable[newY][newX])
         *  3. heights[newY][newX] >= heights[y][x]
         *
         *
         *  NOTE !!!
         *
         *  The condition !reachable[newY][newX] in the dfs function
         *  ensures that each cell is only processed once
         *
         *  1. Avoid Infinite Loops
         *  2. Efficiency
         *  3. Correctness
         *
         *
         *  NOTE !!! "inverse" comparison
         *
         *  we use the "inverse" comparison, e.g.  heights[newY][newX] >= heights[y][x]
         *  so we start from "cur point" (heights[y][x]), and compare with "next point" (heights[newY][newX])
         *  if "next point" is "higher" than "cur point"  (e.g. heights[newY][newX] >= heights[y][x])
         *  -> then means water at "next point" can flow to "cur point"
         *  -> then we keep track back to next point of then "next point"
         *  -> repeat ...
         */
        if (newY >= 0 && newY < l && newX >= 0 && newX < w && !reachable[newY][newX] && heights[newY][newX] >= heights[y][x]) {
            dfs(heights, reachable, newY, newX);
        }
    }
} 

# 2-12) Minesweeper

// java
// LC 529

// (there is also BFS solution)

// V1
// IDEA: DFS + ARRAY OP (GPT)
public char[][] updateBoard_1(char[][] board, int[] click) {
    int rows = board.length;
    int cols = board[0].length;

    int x = click[0], y = click[1];

    // Edge case: 1x1 grid
    if (rows == 1 && cols == 1) {
        if (board[0][0] == 'M') {
            board[0][0] = 'X';
        } else {
            board[0][0] = 'B'; // Fix: properly set 'B' if it's 'E'
        }
        return board;
    }

    // If a mine is clicked, mark as 'X'
    if (board[x][y] == 'M') {
        board[x][y] = 'X';
        return board;
    }

    // Otherwise, reveal cells recursively
    reveal_1(board, x, y);
    return board;
}

private void reveal_1(char[][] board, int x, int y) {
    int rows = board.length;
    int cols = board[0].length;

// Boundary check and already revealed check
/** NOTE !!!
 *
 *  - 1) 'E' represents an unrevealed empty square,
 *
 *  - 2) board[x][y] != 'E'
 *      -> ensures that we only process unrevealed empty cells ('E')
 *         and avoid unnecessary recursion.
 *
 *   - 3) board[x][y] != 'E'
 *   •  Avoids re-processing non-‘E’ cells
 *   •  The board can have:
 *      •   'M' → Mine (already handled separately)
 *      •   'X' → Clicked mine (game over case)
 *      •   'B' → Blank (already processed)
 *      •   '1' to '8' → Number (already processed)
 *  •   If a cell is not 'E', it means:
 *      •   It has already been processed
 *      •   It does not need further expansion
 *  •   This prevents infinite loops and redundant checks.
 *
 *
 *  - 4) example:
 *
 *     input:
 *          E E E
 *          E M E
 *          E E E
 *
 *   Click at (0,0)
 *      1.  We call reveal(board, 0, 0), which:
 *          •   Counts 1 mine nearby → Updates board[0][0] = '1'
 *          •   Does NOT recurse further, avoiding unnecessary work.
 *
 *      What If We Didn’t Check board[x][y] != 'E'?
 *          •   It might try to expand into already processed cells, leading to redundant computations or infinite recursion.
 *
 */
if (x < 0 || x >= rows || y < 0 || y >= cols || board[x][y] != 'E') {
        return;
    }

    // Directions for 8 neighbors
    int[][] directions = {
            { -1, -1 }, { -1, 0 }, { -1, 1 },
            { 0, -1 }, { 0, 1 },
            { 1, -1 }, { 1, 0 }, { 1, 1 }
    };

    // Count adjacent mines
    int mineCount = 0;
    for (int[] dir : directions) {
        int newX = x + dir[0];
        int newY = y + dir[1];
        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && board[newX][newY] == 'M') {
            mineCount++;
        }
    }

    // If there are adjacent mines, show count
    if (mineCount > 0) {
        board[x][y] = (char) ('0' + mineCount);
    } else {
        // Otherwise, reveal this cell and recurse on neighbors
        board[x][y] = 'B';
        for (int[] dir : directions) {
            reveal_1(board, x + dir[0], y + dir[1]);
        }
    }
}

# 2-13) K-th Largest Perfect Subtree Size in Binary Tree

// java
// LC 3319

// V0-1
// IDEA: DFS (fixed by gpt)
//  Time Complexity: O(N log N)
//  Space Complexity: O(N)
/**
*  Objective recap:
*
*   We want to:
*    •   Find all perfect binary subtrees in the given tree.
*    •   A perfect binary tree is one where:
*        •   Every node has 0 or 2 children (i.e., full),
*        •   All leaf nodes are at the `same depth`.
*    •   Return the k-th largest size among these perfect subtrees.
*    •   If there are fewer than k perfect subtrees, return -1.
*
*/
// This is a class-level list that stores the sizes of all perfect subtrees we discover during traversal.
List<Integer> perfectSizes = new ArrayList<>();

public int kthLargestPerfectSubtree_0_1(TreeNode root, int k) {
    dfs(root);
    if (perfectSizes.size() < k)
        return -1;

    Collections.sort(perfectSizes, Collections.reverseOrder());
    return perfectSizes.get(k - 1);
}

// Helper class to store information about each subtree
/**
*
* It returns a helper object SubtreeInfo, which contains:
*    •   height: depth of the subtree rooted at node.
*    •   size: number of nodes in the subtree.
*    •   isPerfect: boolean indicating whether this subtree is perfect.
*
*/
private static class SubtreeInfo {
    int height;
    int size;
    boolean isPerfect;

    SubtreeInfo(int height, int size, boolean isPerfect) {
        this.height = height;
        this.size = size;
        this.isPerfect = isPerfect;
    }
}

/**
* Inside dfs():
*    1.  Base case:
*        •   If node == null, we return a SubtreeInfo with height 0, size 0, and isPerfect = true.
*    2.  Recurse on left and right children.
*    3.  Check if the subtree rooted at this node is perfect:
*
*/
private SubtreeInfo dfs(TreeNode node) {
    if (node == null) {
        return new SubtreeInfo(0, 0, true);
    }

    SubtreeInfo left = dfs(node.left);
    SubtreeInfo right = dfs(node.right);

/**  NOTE !!!  below logic:
 *
 * This ensures:
 *  •   Both left and right subtrees are perfect.
 *  •   Their `heights` are the same → leaves are at the `same level`.
 */
boolean isPerfect = left.isPerfect && right.isPerfect
        && (left.height == right.height);


    int size = left.size + right.size + 1;
    int height = Math.max(left.height, right.height) + 1;

    /**
     *  NOTE !!!
     *
     *  If the current subtree is perfect, we record its size:
     *
     */
    if (isPerfect) {
        perfectSizes.add(size);
    }

    return new SubtreeInfo(height, size, isPerfect);
}

# Pattern Selection Strategy

DFS Problem Analysis Flowchart:

1. Is it a tree/graph traversal problem?
   ├── YES → Check structure type
   │   ├── Tree? → Use Tree Templates (1, 3, 5, 6)
   │   │   ├── Need specific order? → Template 1 (Traversal)
   │   │   ├── Need paths? → Template 3 (Path Finding)
   │   │   ├── Need to modify? → Template 5 (Modification)
   │   │   └── Need subtree info? → Template 6 (Bottom-up)
   │   └── Graph? → Use Graph Template (2)
   │       ├── Has cycles? → Add visited set
   │       ├── Need all paths? → Track path
   │       └── Multi-source? → Start from all sources
   └── NO → Continue to 2

2. Is it a combinatorial problem?
   ├── YES → Use Backtracking Template (4)
   │   ├── Permutations? → Swap elements
   │   ├── Combinations? → Start index
   │   ├── Subsets? → Include/exclude
   │   └── Constraint satisfaction? → Check validity
   └── NO → Continue to 3

3. Does it require exploring all possibilities?
   ├── YES → Use DFS with appropriate state tracking
   │   ├── Grid problem? → 4-directional DFS
   │   ├── String problem? → Index-based DFS
   │   └── Decision tree? → Choice-based DFS
   └── NO → Consider different algorithm

4. Special considerations:
   ├── Need shortest path? → Consider BFS instead
   ├── Has optimal substructure? → Consider DP
   └── Need all solutions? → DFS with backtracking

# Decision Framework

1. Identify problem type: Tree, graph, grid, or combinatorial
2. Choose template: Match problem requirements to template
3. Handle state: Decide what to track (visited, path, sum)
4. Optimize: Consider memoization, pruning, early termination

# Summary & Quick Reference

# Complexity Quick Reference

Pattern	Time Complexity	Space Complexity	Notes
Tree Traversal	O(n)	O(h)	h = height
Graph DFS	O(V + E)	O(V)	V = vertices, E = edges
Grid DFS	O(m × n)	O(m × n)	m×n grid
Backtracking	O(b^d)	O(d)	b = branching, d = depth
Path Finding	O(n)	O(h)	May need O(n) for all paths
Bottom-up	O(n)	O(h)	Single pass with aggregation

# Template Quick Reference

Template	Best For	Avoid When	Key Pattern
Tree Traversal	Visiting all nodes	Need shortest path	Pre/in/post order
Graph DFS	Connected components	Has negative cycles	Visited set
Path Finding	Root-to-leaf paths	Any path works	Track & backtrack
Backtracking	All combinations	Single solution needed	Make/unmake choice
Modification	Tree editing	Read-only required	Bottom-up update
Bottom-up	Subtree aggregation	Simple traversal	Post-order return

# Common Patterns & Tricks

# Pattern: Global Variable for Optimization

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        
        def dfs(node):
            if not node:
                return 0
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            self.max_sum = max(self.max_sum, left + right + node.val)
            return max(left, right) + node.val
        
        dfs(root)
        return self.max_sum

# Pattern: Path Tracking with Backtracking

def all_paths(root):
    result = []
    
    def dfs(node, path):
        if not node:
            return
        
        path.append(node.val)  # Make choice
        
        if not node.left and not node.right:
            result.append(path[:])  # Found complete path
        
        dfs(node.left, path)
        dfs(node.right, path)
        
        path.pop()  # Unmake choice (backtrack)
    
    dfs(root, [])
    return result

# Pattern: Grid DFS with Directions

def grid_dfs(grid, x, y, visited):
    if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
        return
    if (x, y) in visited or grid[x][y] == 0:
        return
    
    visited.add((x, y))
    
    # 4-directional movement
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    for dx, dy in directions:
        grid_dfs(grid, x + dx, y + dy, visited)

# Problem-Solving Steps

1. Identify pattern: Tree, graph, backtracking, or path
2. Choose template: Select appropriate DFS template
3. Track state: Visited set, path list, or global variable
4. Handle base cases: Null nodes, boundaries, target found
5. Test edge cases: Empty input, single node, cycles

# Common Mistakes & Tips

🚫 Common Mistakes:

• Forgetting visited set: Infinite loops in graphs
• Not backtracking: Incorrect paths in combinatorial problems
• Wrong traversal order: Using preorder when postorder needed
• Modifying while traversing: Can break iteration
• Not handling null: NullPointerException
• ⚠️ CRITICAL: Not returning immediately when path found: When searching for a path in DFS, must return true immediately when found (see detailed explanation below)

✅ Best Practices:

• Use visited set for graphs: Prevent cycles
• Clone paths: path[:] when storing results
• Check boundaries first: In grid problems
• Use meaningful names: visited not v
• Consider iterative: For deep recursion

# Interview Tips

1. Clarify problem type: Tree or graph? Cycles possible?
2. State approach: “I’ll use DFS because…”
3. Discuss complexity: Time and space analysis
4. Handle edge cases: Empty, single element, cycles
5. Optimize if needed: Memoization, pruning

---

# ⚠️ CRITICAL: DFS Early Return Pattern (Path Finding)

Problem: When searching for a path in DFS, what’s the difference between these two approaches?

# ❌ WRONG Approach: Not Checking Return Value

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ❌ WRONG: Ignoring return value - continues searching even after path found!
            dfsPathVisitor(next, destination, map, visited);
        }
    }

    return false;  // Will ALWAYS return false (except for direct hits)
}

# ✅ CORRECT Approach: Early Return on Success

private boolean dfsPathVisitor(int node, int destination, Map<Integer, List<Integer>> map, boolean[] visited) {
    if (node == destination) return true;

    visited[node] = true;

    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ✅ CORRECT: Return immediately when path found!
            if (dfsPathVisitor(next, destination, map, visited)) {
                return true;
            }
        }
    }

    return false;  // Only return false if ALL paths explored
}

---

# 📊 Concrete Example: Why Early Return Matters

Test Case:

Graph: 0 -- 1 -- 2 -- 3
       |         |
       4 -------- 5

Adjacency List:
0: [1, 4]
1: [0, 2]
2: [1, 3, 5]
3: [2]
4: [0, 5]
5: [2, 4]

Task: Find path from 0 to 3

---

# Scenario 1: ❌ WRONG (Without Early Return)

Call Stack Trace:

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0, already visited)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← But level 2 IGNORES the return value!
      ← Continues checking neighbor 5

      5. dfsPathVisitor(5, 3, ..., visited=[0,1,2])
         → visited = [0, 1, 2, 5]
         → Loop neighbors: [2, 4]  (both visited)
         ← Returns FALSE

      ← Level 2 finishes loop, returns FALSE

   ← Level 1 receives FALSE from neighbor 1

   6. dfsPathVisitor(4, 3, ..., visited=[0,1,2,5])  // Second neighbor
      → visited = [0, 1, 2, 5, 4]
      → Loop neighbors: [0, 5]  (both visited)
      ← Returns FALSE

   ← Level 0 finishes loop, returns FALSE

❌ FINAL RESULT: FALSE (Path exists but not detected!)

Why it fails:

• Found destination at step 4 (returned TRUE)
• But parent call at step 3 ignored the TRUE result
• Continued exploring other neighbors unnecessarily
• Eventually returned FALSE because other paths didn’t reach destination

---

# Scenario 2: ✅ CORRECT (With Early Return)

Call Stack Trace:

1. dfsPathVisitor(0, 3, ..., visited=[])
   → visited = [0]
   → Loop neighbors: [1, 4]

   2. dfsPathVisitor(1, 3, ..., visited=[0])  // First neighbor
      → visited = [0, 1]
      → Loop neighbors: [0, 2]  (skip 0)

      3. dfsPathVisitor(2, 3, ..., visited=[0,1])
         → visited = [0, 1, 2]
         → Loop neighbors: [1, 3, 5]  (skip 1)

         4. dfsPathVisitor(3, 3, ..., visited=[0,1,2])
            → ✅ Found! Returns TRUE

         ← Returns TRUE to level 3

      ← Level 2 checks: if (TRUE) return true;  ✅
      ← Returns TRUE immediately (skips remaining neighbors!)

   ← Level 1 checks: if (TRUE) return true;  ✅
   ← Returns TRUE immediately (skips neighbor 4!)

✅ FINAL RESULT: TRUE (Correct!)

Why it works:

• Found destination at step 4 (returned TRUE)
• Parent call at step 3 checked the return value
• Immediately returned TRUE without exploring other paths
• Propagated TRUE all the way back to the root

---

# 🎯 Key Insights

Aspect	❌ Without Early Return	✅ With Early Return
Correctness	❌ Returns FALSE even when path exists	✅ Returns TRUE when path found
Efficiency	Explores ALL paths unnecessarily	Stops immediately upon finding path
Time Complexity	O(V + E) always (full traversal)	O(V + E) worst case, but often much better
Use Case	Collecting ALL paths/results	Finding ANY path (exists/not exists)

---

# 📝 When to Use Each Pattern

# Pattern 1: Early Return (Path Existence Check)

// Use when: "Does path exist?" "Can we reach?" "Is there a route?"
if (dfs(next)) {
    return true;  // Found one path - that's enough!
}

Examples: LC 1971 (Path Exists), LC 797 (All Paths), LC 79 (Word Search)

# Pattern 2: Continue Without Return (Collecting All Results)

// Use when: "Find ALL paths" "Count all solutions" "Collect all combinations"
dfs(next);  // Don't return early - need to explore all branches

Examples: LC 257 (All Root-to-Leaf Paths), LC 113 (Path Sum II), LC 22 (Generate Parentheses)

---

# 🔍 Real Implementation Reference

From LC 1971 - Find if Path Exists in Graph:

private boolean dfsPathVisitor(int node, int destination,
                                Map<Integer, List<Integer>> map,
                                boolean[] visited) {
    // Base case: destination reached
    if (node == destination)
        return true;

    // Mark current node as visited
    visited[node] = true;

    // Visit neighbors
    for (int next : map.get(node)) {
        if (!visited[next]) {
            // ✅ CRITICAL: Check return value and return immediately if path found
            if (dfsPathVisitor(next, destination, map, visited)) {
                return true;
            }

            // ❌ WRONG PATTERN (commented out):
            // if (!dfsPathVisitor(next, destination, map, visited)) {
            //     return false;  // This would fail for graphs with multiple paths!
            // }
        }
    }

    return false;  // Only return false if ALL neighbors failed
}

Key Rule:

• Return TRUE eagerly (as soon as found)
• Return FALSE lazily (only after exhausting all options)

---

# Related Topics

• BFS: When shortest path needed
• Dynamic Programming: Overlapping subproblems
• Backtracking: Subset of DFS for combinations
• Union Find: Alternative for connectivity
• Topological Sort: DFS application for dependencies

# 2-14) Number of Distinct Islands

// java
// LC 694
// V0
// IDEA: DFS + Path Signatures (Directional Encoding)
/**
 * Problem: Count distinct island shapes (translation-invariant)
 *
 * Key Insight: Two islands are the same if one can be translated (NOT rotated/reflected) to match the other
 *
 * Solution Approach:
 * 1. For each island, generate a unique "path signature" encoding its shape
 * 2. Use a HashSet to count distinct signatures
 * 3. Signature must be translation-invariant but rotation/reflection-sensitive
 *
 * Critical Implementation Details:
 * - Canonical traversal order (always D, U, R, L)
 * - Starting point normalization (top-left via grid iteration order)
 * - Backtracking delimiter ('O') to distinguish shapes
 */
public int numDistinctIslands(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    Set<String> uniqueIslandShapes = new HashSet<>();
    int rows = grid.length;
    int cols = grid[0].length;

    // Iterate through grid in fixed order (top-to-bottom, left-to-right)
    // This ensures the starting point for each island is always the top-left-most cell
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            // Start DFS only on unvisited land cells
            if (grid[r][c] == 1) {
                StringBuilder pathSignature = new StringBuilder();
                // 'S' marks the start position
                dfs(grid, r, c, pathSignature, 'S');

                if (pathSignature.length() > 0) {
                    uniqueIslandShapes.add(pathSignature.toString());
                }
            }
        }
    }

    return uniqueIslandShapes.size();
}

/**
 * DFS with directional encoding
 *
 * @param grid The grid, modified in-place (cells set to 0 when visited)
 * @param r Current row
 * @param c Current column
 * @param path StringBuilder to build the signature
 * @param direction Direction taken to arrive at (r, c)
 */
private void dfs(int[][] grid, int r, int c, StringBuilder path, char direction) {
    int rows = grid.length;
    int cols = grid[0].length;

    // Base Case 1: Out of bounds
    if (r < 0 || r >= rows || c < 0 || c >= cols) {
        return;
    }

    // Base Case 2: Water (0) or already visited land (already marked as 0)
    if (grid[r][c] == 0) {
        return;
    }

    // 1. Mark the current cell as visited by setting it to water (0)
    // This prevents double counting and replaces the need for a separate visited array
    grid[r][c] = 0;

    // 2. Record the direction of movement into this cell
    path.append(direction);

    // 3. Recurse into neighbors in FIXED order (critical for consistency!)
    // The order must always be the same to ensure identical islands produce identical signatures
    dfs(grid, r + 1, c, path, 'D');  // Down
    dfs(grid, r - 1, c, path, 'U');  // Up
    dfs(grid, r, c + 1, path, 'R');  // Right
    dfs(grid, r, c - 1, path, 'L');  // Left

    // 4. Crucial Step: Add an "Out" (O) delimiter when returning from this cell
    // This marks the end of a branch and distinguishes shapes that follow different paths
    // Without this, different shapes could produce the same signature!
    path.append('O');
}

// V1
// IDEA: Alternative approach using relative coordinates
/**
 * Instead of directional encoding, record relative positions from the starting point
 */
public int numDistinctIslands_v2(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Set<String> shapes = new HashSet<>();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (!seen[r][c] && grid[r][c] == 1) {
                StringBuilder sb = new StringBuilder();
                // Pass starting coordinates (r, c) as origin
                dfsRelative(grid, seen, r, c, r, c, sb);
                shapes.add(sb.toString());
            }
        }
    }
    return shapes.size();
}

/**
 * DFS that records relative coordinates from origin (r0, c0)
 */
private void dfsRelative(int[][] grid, boolean[][] seen, int r0, int c0, int r, int c, StringBuilder sb) {
    int rows = grid.length, cols = grid[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (seen[r][c] || grid[r][c] != 1) return;

    seen[r][c] = true;
    // Record relative position: (r - r0, c - c0)
    // This makes the signature translation-invariant
    sb.append((r - r0)).append('_').append((c - c0)).append(',');

    // Visit in fixed order (critical!)
    dfsRelative(grid, seen, r0, c0, r + 1, c, sb);
    dfsRelative(grid, seen, r0, c0, r - 1, c, sb);
    dfsRelative(grid, seen, r0, c0, r, c + 1, sb);
    dfsRelative(grid, seen, r0, c0, r, c - 1, sb);
}

# python
# LC 694
# V0
# IDEA: DFS + Path Signatures
def numDistinctIslands(grid):
    """
    Count distinct island shapes using directional path encoding

    Example:
    Input: grid = [[1,1,0,0,0],
                   [1,1,0,0,0],
                   [0,0,0,1,1],
                   [0,0,0,1,1]]
    Output: 1
    Explanation: Both islands have the same shape

    The path signature for both islands would be: "SDROO" or similar
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    unique_shapes = set()

    def dfs(r, c, direction, path):
        # Out of bounds or water/visited
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        # Mark as visited
        grid[r][c] = 0

        # Record direction
        path.append(direction)

        # Visit in fixed order: Down, Up, Right, Left
        dfs(r + 1, c, 'D', path)
        dfs(r - 1, c, 'U', path)
        dfs(r, c + 1, 'R', path)
        dfs(r, c - 1, 'L', path)

        # Add backtrack delimiter
        path.append('O')

    # Process each island
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, 'S', path)  # 'S' for start
                unique_shapes.add(tuple(path))

    return len(unique_shapes)

Why This Works:

1. Starting Point Normalization

   • Grid iteration is top-to-bottom, left-to-right
   • First land cell encountered is always the top-left-most cell of the island
   • This guarantees the same starting point for identical shapes

2. Canonical Traversal Order

   • Always check: Down (D), Up (U), Right ®, Left (L) in that order
   • Same shape always produces same sequence of directions

3. Backtrack Delimiter (‘O’)

   Example showing why delimiter is needed:
   
   Shape A:  11     Path without 'O': SDRO
              1     Path with 'O':    SDROO
   
   Shape B:   1     Path without 'O': SDRO (Same as A - WRONG!)
             11     Path with 'O':    SDORO (Different - CORRECT!)
   

4. Translation Invariance

   • Only records directions/relative positions, not absolute coordinates
   • Islands with same shape but different positions → same signature

Time Complexity: O(m × n) where m = rows, n = cols Space Complexity: O(m × n) for recursion stack and HashSet

# Java Implementation Notes

// Java DFS with Stack
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // Process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

// Graph DFS with adjacency list
void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}

# Python Implementation Notes

# Using collections.deque as stack
from collections import deque
stack = deque([root])
while stack:
    node = stack.pop()  # pop() for stack behavior
    # Process node

# Graph representation
graph = defaultdict(list)  # Adjacency list
visited = set()  # Track visited nodes

# Recursion limit for deep trees
import sys
sys.setrecursionlimit(10000)

---

Must-Know Problems for Interviews: LC 94, 104, 112, 113, 124, 200, 236, 297, 399, 694 Advanced Problems: LC 124, 297, 329, 472, 652, 694, 711 Path Signature Pattern: LC 694 (Distinct Islands), LC 711 (Distinct Islands II), LC 652 (Find Duplicate Subtrees) Keywords: DFS, depth-first search, recursion, tree traversal, graph traversal, backtracking, path signatures, shape encoding