DFS — Worked Examples

# python
# LC 655 - Print Binary Tree
# IDEA: height first; then pre-order DFS places each node and halves the column offset per level
# time = O(h * 2^h), space = O(h * 2^h)   the output grid is (h + 1) x (2^(h+1) - 1)
def printTree(root):
    def height(node):
        if not node:
            return -1                      # a lone leaf has height 0
        return 1 + max(height(node.left), height(node.right))

    h = height(root)
    rows, cols = h + 1, 2 ** (h + 1) - 1
    grid = [[""] * cols for _ in range(rows)]

    def place(node, row, col):
        if not node:
            return
        grid[row][col] = str(node.val)
        if row == h:
            return
        offset = 2 ** (h - row - 1)        # halves on every level down
        place(node.left, row + 1, col - offset)
        place(node.right, row + 1, col + offset)

    place(root, 0, (cols - 1) // 2)        # root in the middle of the top row
    return grid

# python
# LC 695 - Max Area of Island
# IDEA: each 1 still standing starts a sink that returns the island's size; keep the largest
# time = O(m * n), space = O(m * n)   the recursion is as deep as the largest island
def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0                     # sink on entry: never counted twice
        return 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1)

    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                best = max(best, sink(r, c))
    return best

// java
// LC 695 - Max Area of Island
// IDEA: flood fill that returns the size of the island it sinks; keep the largest
// time = O(m * n), space = O(m * n)
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                best = Math.max(best, area(grid, r, c));
            }
        }
        return best;
    }

    private int area(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0;                           // sink it so it is counted once
        return 1 + area(grid, r + 1, c) + area(grid, r - 1, c)
                 + area(grid, r, c + 1) + area(grid, r, c - 1);
    }
}

# python
# LC 529 - Minesweeper
# IDEA: a mine click is game over; otherwise flood from the click, stopping at cells next to a mine
# time = O(m * n), space = O(m * n)   each cell is revealed once; recursion as deep as the blank region
import sys
sys.setrecursionlimit(10**6)   # the default 1,000 is too low: a 50 x 50 blank board recurses 2,500 deep

def updateBoard(board, click):
    rows, cols = len(board), len(board[0])
    r, c = click
    if board[r][c] == "M":
        board[r][c] = "X"
        return board
    dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    def reveal(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "E":
            return                         # only an unrevealed empty cell expands
        mines = 0
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "M":
                mines += 1
        if mines > 0:
            board[r][c] = str(mines)       # a number stops the flood
            return
        board[r][c] = "B"
        for dr, dc in dirs:
            reveal(r + dr, c + dc)

    reveal(r, c)
    return board

# python
# LC 737 - Sentence Similarity II
# IDEA: undirected graph of similar pairs; each differing word pair must be reachable
# time = O(n * (V + E)), space = O(V + E)   one DFS per aligned pair, n = sentence length
from collections import defaultdict

def areSentencesSimilarTwo(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2):
        return False
    graph = defaultdict(set)
    for a, b in similarPairs:
        graph[a].add(b)
        graph[b].add(a)                    # similarity is symmetric: both directions

    def connected(src, dst):
        stack, seen = [src], {src}
        while stack:
            word = stack.pop()
            if word == dst:
                return True
            for nxt in graph[word]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
        return False

    for w1, w2 in zip(sentence1, sentence2):
        if w1 != w2 and not connected(w1, w2):
            return False
    return True

# python
# LC 990 - Satisfiability of Equality Equations
# IDEA: DFS labels each == component; a != inside one component is a contradiction
# time = O(n), space = O(1)   n = equations; at most 26 variables
from collections import defaultdict

def equationsPossible(equations):
    graph = defaultdict(list)
    for eq in equations:
        if eq[1] == "=":
            graph[eq[0]].append(eq[3])
            graph[eq[3]].append(eq[0])     # == is symmetric: store both directions

    group = {}
    def label(var, gid):
        group[var] = gid
        for nxt in graph[var]:
            if nxt not in group:
                label(nxt, gid)

    for var in list(graph):
        if var not in group:
            label(var, var)                # one DFS per component

    for eq in equations:
        if eq[1] == "!":
            a, b = eq[0], eq[3]
            if a == b or (a in group and group.get(b) == group[a]):
                return False
    return True

# python
# LC 472 - Concatenated Words
# IDEA: a word counts if a proper dictionary prefix leaves a suffix that splits into dictionary words
# time = O(n * L^3), space = O(n * L)   n words of length L: L suffixes, L cuts each, O(L) slicing
def findAllConcatenatedWordsInADict(words):
    word_set = set(words)
    memo = {}

    def splits(word):
        # can `word` be cut into one or more dictionary words?
        if word in memo:
            return memo[word]
        for i in range(1, len(word) + 1):
            prefix = word[:i]
            if prefix in word_set and (i == len(word) or splits(word[i:])):
                memo[word] = True
                return True
        memo[word] = False
        return False

    result = []
    for word in words:
        if not word:
            continue
        # two or more pieces: the first piece is a PROPER prefix
        for i in range(1, len(word)):
            if word[:i] in word_set and splits(word[i:]):
                result.append(word)
                break
    return result

# python
# LC 663 - Equal Tree Partition
# IDEA: post-order collects every subtree sum; look for total / 2 among the proper subtrees
# time = O(n), space = O(n)
def checkEqualTree(root):
    sums = []

    def subtree_sum(node):
        if not node:
            return 0
        s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
        sums.append(s)
        return s

    total = subtree_sum(root)
    sums.pop()                             # the whole tree is the last sum: not a cut
    return total % 2 == 0 and total // 2 in sums

# python
# LC 1339 - Maximum Product of Splitted Binary Tree
# IDEA: post-order records every subtree sum s; each is one cut worth s * (total - s)
# time = O(n), space = O(n)
def maxProduct(root):
    sums = []

    def subtree_sum(node):
        if not node:
            return 0
        s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
        sums.append(s)
        return s

    total = subtree_sum(root)
    best = 0
    for s in sums:
        best = max(best, s * (total - s))
    return best % (10 ** 9 + 7)            # take the max BEFORE the modulo

# python
# LC 3319 - K-th Largest Perfect Subtree Size in Binary Tree
# IDEA: post-order returns (height, is_perfect); record 2^height - 1 for every perfect subtree
# time = O(n log n), space = O(n)   the sort of the recorded sizes dominates
import sys
sys.setrecursionlimit(10**6)   # the default 1,000 is too low: a 2,000-node chain recurses 2,000 deep

def kthLargestPerfectSubtree(root, k):
    sizes = []

    def dfs(node):
        if not node:
            return 0, True
        left_h, left_ok = dfs(node.left)
        right_h, right_ok = dfs(node.right)
        if left_ok and right_ok and left_h == right_h:
            sizes.append(2 ** (left_h + 1) - 1)
            return left_h + 1, True
        return max(left_h, right_h) + 1, False

    dfs(root)
    if len(sizes) < k:
        return -1
    sizes.sort(reverse=True)
    return sizes[k - 1]

# python
# LC 417 - Pacific Atlantic Water Flow
# IDEA: flood uphill from each ocean's border; answer = cells reached by both floods
# time = O(m * n), space = O(m * n)   each flood visits a cell at most once
import sys
sys.setrecursionlimit(10**6)   # the default 1,000 is too low: a flat 200 x 200 grid recurses 40,000 deep

def pacificAtlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pacific, atlantic = set(), set()

    def climb(r, c, reached):
        reached.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in reached
                    and heights[nr][nc] >= heights[r][c]):   # uphill: its water flows down to us
                climb(nr, nc, reached)

    for r in range(rows):
        climb(r, 0, pacific)               # left edge
        climb(r, cols - 1, atlantic)       # right edge
    for c in range(cols):
        climb(0, c, pacific)               # top edge
        climb(rows - 1, c, atlantic)       # bottom edge

    result = []
    for r in range(rows):
        for c in range(cols):
            if (r, c) in pacific and (r, c) in atlantic:
                result.append([r, c])
    return result