04 — Trees, Tries, Heaps#

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# DFS PREORDER: node → left → right
# Use when: you need to process a node BEFORE its children (copying a tree,
# serialization, path-building from the root down)
def preorder(node, out):
    if not node: return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
 
# DFS INORDER: left → node → right
# Use when: BST — this yields values in SORTED order. Huge.
def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
# DFS POSTORDER: left → right → node
# Use when: you need children's answers BEFORE computing the node's
# (height, diameter, subtree sums, deletion, "is this subtree valid")
def postorder(node, out):
    if not node: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)
 
# BFS LEVEL ORDER: level by level, left to right
# Use when: levels matter, or you need the SHORTEST path/minimum depth
from collections import deque
def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # snapshot the size — this is the trick
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

# Maximum Depth
def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
 
# Balanced Binary Tree — O(n), computing height and balance together
def is_balanced(root):
    def height(node):
        if not node: return 0
        lh = height(node.left)
        if lh == -1: return -1            # -1 propagates "unbalanced" upward
        rh = height(node.right)
        if rh == -1: return -1
        if abs(lh - rh) > 1: return -1
        return 1 + max(lh, rh)
    return height(root) != -1

# Diameter of Binary Tree — longest path between ANY two nodes
def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node: return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)        # path THROUGH this node
        return 1 + max(lh, rh)           # but only ONE side goes to the parent
    height(root)
    return best

def max_path_sum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node: return 0
        l = max(gain(node.left), 0)      # clamp at 0 — skip negative branches
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)   # path through this node
        return node.val + max(l, r)          # extendable path to parent
    gain(root)
    return best

# Validate BST — the bounds must narrow as you descend
def is_valid_bst(root):
    def check(node, low, high):
        if not node: return True
        if not (low < node.val < high): return False
        return (check(node.left,  low, node.val) and
                check(node.right, node.val, high))
    return check(root, float('-inf'), float('inf'))

# Count Good Nodes — a node is good if no ancestor is larger
def good_nodes(root):
    def dfs(node, max_so_far):
        if not node: return 0
        good = 1 if node.val >= max_so_far else 0
        max_so_far = max(max_so_far, node.val)
        return good + dfs(node.left, max_so_far) + dfs(node.right, max_so_far)
    return dfs(root, root.val)

# Search — O(h)
def search_bst(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root
 
# Lowest Common Ancestor in a BST — O(h), exploits the ordering
def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left            # both on the left
        elif p.val > root.val and q.val > root.val:
            root = root.right           # both on the right
        else:
            return root                 # they split here → this is the LCA
 
# LCA in a GENERAL binary tree — no ordering to exploit
def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right: return root      # found in both subtrees → root is LCA
    return left or right                # otherwise pass up whichever we found
 
# Kth Smallest in a BST — inorder gives sorted order
def kth_smallest(root, k):
    stack, curr = [], root
    while stack or curr:
        while curr:                     # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0: return curr.val
        curr = curr.right

# Build from preorder + inorder
def build_tree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}      # O(1) root lookup
    self_pre = [0]                                   # mutable cursor
 
    def build(lo, hi):
        if lo > hi: return None
        root_val = preorder[self_pre[0]]
        self_pre[0] += 1
        node = TreeNode(root_val)
        mid = idx[root_val]
        node.left  = build(lo, mid - 1)     # preorder: left is built first
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(inorder) - 1)
# O(n) with the index map; O(n²) without it (searching inorder each time)

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node:
                out.append("#")          # explicit null marker
                return
            out.append(str(node.val))
            dfs(node.left); dfs(node.right)
        dfs(root)
        return ",".join(out)
 
    def deserialize(self, data):
        vals = iter(data.split(","))
        def build():
            v = next(vals)
            if v == "#": return None
            node = TreeNode(int(v))
            node.left = build()
            node.right = build()
            return node
        return build()

class TrieNode:
    def __init__(self):
        self.children = {}          # char -> TrieNode
        self.is_word = False        # marks the end of a complete word
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        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, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

class WordDictionary:
    """Supports '.' matching any single character."""
    def __init__(self):
        self.root = TrieNode()
 
    def addWord(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_word = True
 
    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_word
            c = word[i]
            if c == '.':
                return any(dfs(child, i + 1) for child in node.children.values())
            return c in node.children and dfs(node.children[c], i + 1)
        return dfs(self.root, 0)

def find_words(board, words):
    root = TrieNode()
    for w in words:                        # build the trie
        node = root
        for c in w:
            node = node.children.setdefault(c, TrieNode())
        node.word = w                       # store the full word at the end
 
    rows, cols = len(board), len(board[0])
    found = set()
 
    def dfs(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        ch = board[r][c]
        if ch not in node.children:        # PRUNE — no word has this prefix
            return
        nxt = node.children[ch]
        if getattr(nxt, 'word', None):
            found.add(nxt.word)
        board[r][c] = '#'                  # mark visited
        for dr, dc in ((0,1),(1,0),(0,-1),(-1,0)):
            dfs(r + dr, c + dc, nxt)
        board[r][c] = ch                   # backtrack — restore
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return list(found)