Blind 75 Trees And Tries

Helper contract: max_depth(node) returns the number of nodes on the longest downward path starting at node. An empty subtree contributes zero. Test empty tree, one node, and a skewed chain to catch off-by-one errors.

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Compare both structure and value at the same time. The common mistake is returning true when one side is empty and the other is not. A pair of empty nodes matches; exactly one empty node does not.

def is_same_tree(p, q):
    if p is None or q is None:
        return p is q
    return (
        p.val == q.val
        and is_same_tree(p.left, q.left)
        and is_same_tree(p.right, q.right)
    )

Preorder or postorder both work because each subtree is independent. Swap the children, then recursively invert the children now attached to the opposite side. Test with asymmetric trees; symmetric trees can hide incorrect swaps.

def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

The helper returns the best one-sided gain that can extend to the parent. The global answer may use both left and right gains at the current node, but that split path cannot be returned upward because it would branch. Clamp negative child gains to zero.

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0

        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

Each node must be strictly inside the range inherited from all ancestors. Checking only direct children misses cases where a node in the right subtree is smaller than the root. Ask whether duplicates are allowed; Blind 75 usually treats them as invalid.

def is_valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float("-inf"), float("inf"))

Inorder traversal visits BST values in sorted order. The stack stores the path to the next unvisited smallest node. Common mistakes are decrementing k before visiting a node or forgetting to move to the right subtree after a visit.

def kth_smallest(root, k):
    stack = []
    node = root

    while stack or node:
        while node:
            stack.append(node)
            node = node.left

        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

    raise ValueError("k is larger than the number of nodes")

If both target values are smaller than the current value, move left. If both are larger, move right. Otherwise the current node is the split point and therefore the lowest common ancestor. Test when one target is the ancestor of the other.

Each node maps characters to child nodes and records whether a word ends at that node. A prefix can exist without being a full word. Test inserting app and apple, then search both app and ap.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Build a trie so DFS can stop as soon as a prefix is impossible. The visited mark belongs to the current path only, so restore the board cell after recursion. Store the full word at terminal trie nodes to avoid rebuilding strings and set it to None after finding it to prevent duplicates.

def find_words(board, words):
    root = {}
    END = "#"
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})
        node[END] = word

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node:
            return

        nxt = node[ch]
        word = nxt.pop(END, None)
        if word is not None:
            found.append(word)

        board[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 board[nr][nc] != "*":
                dfs(nr, nc, nxt)
        board[r][c] = ch

        if not nxt:
            node.pop(ch)

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return found

A trie helps match prefixes and domain terms efficiently as partial transcripts arrive. It can support autocomplete, contextual biasing candidates, and entity highlighting. It does not solve acoustic confusion, tokenization mismatch, pronunciation variants, or language-model scoring by itself. A strong answer adds evaluation: entity recall, false positives, latency per partial, and slice checks for accents and noisy audio.

Treat the rollout config as a decision tree. Each node should have a clear predicate, default path, and inherited constraints. Debug by tracing one affected request from root to leaf, then checking whether child rules accidentally widened an ancestor's scope. Add tests for mutually exclusive branches, default behavior, and representative locale-device-model combinations before deploying.