Recap — BST and Heap Mental Models

# BST and Heap Mental Models Two related-but-distinct ordered tree structures. Each solves a specific problem class. ## Binary Search Tree (BST) Invariant: for every node, left subtree < node < right subtree. ```python class TreeNode: val: int left: 'TreeNode' right: 'TreeNode' ``` ### Operations and complexity | Operation | Average | Worst (unbalanced) | |---|---|---| | Search | O(log N) | O(N) | | Insert | O(log N) | O(N) | | Delete | O(log N) | O(N) | | In-order traversal | O(N) | O(N) | Self-balancing BSTs (AVL, Red-Black) guarantee O(log N) worst case but aren't typically required to implement in interviews — just know the concept. Python doesn't have a built-in BST. Use `sortedcontainers.SortedList` (if allowed) or implement manually. ### When to use BST - Need sorted order AND fast insert/delete. - "Find the smallest/largest in O(log N)." - "Find rank/order of an element." ### BST search ```python def search(node, val): if not node: return None if val == node.val: return node if val < node.val: return search(node.left, val) return search(node.right, val) ``` ### Validate BST A classic interview problem. Use in-order traversal: ```python def is_valid_bst(root): prev = [None] def inorder(node): if not node: return True if not inorder(node.left): return False if prev[0] is not None and node.val = hi: return False return is_valid_bst(node.left, lo, node.val) and is_valid_bst(node.right, node.val, hi) ``` ## Heap (Priority Queue) A complete binary tree where every parent ≤ its children (min-heap) or ≥ (max-heap). Implementation: usually an array. Parent of index i is at (i-1)//2; children at 2i+1, 2i+2. ```python import heapq h = [] heapq.heappush(h, 3) heapq.heappush(h, 1) heapq.heappush(h, 2) heapq.heappop(h) # 1 (always smallest in min-heap) ``` Python's `heapq` is a min-heap. For max-heap, push negatives: ```python heapq.heappush(h, -value) top = -heapq.heappop(h) # largest ``` ### Operations and complexity | Operation | Time | |---|---| | heappush | O(log N) | | heappop | O(log N) | | heappeek (h[0]) | O(1) | | heapify (build from list) | O(N) | ### When to use heap - **Top K** problems. "Find the K largest/smallest." - **Always-the-min/max** access during a stream. - **Dijkstra's shortest path** (priority queue). - **Merge K sorted lists** (heap of head pointers). - **K closest points to origin.** ### Pattern: K largest elements ```python import heapq def k_largest(nums, k): return heapq.nlargest(k, nums) ``` Or manually with a min-heap of size K: ```python def k_largest(nums, k): h = [] for x in nums: heapq.heappush(h, x) if len(h) > k: heapq.heappop(h) # remove smallest; keeps top K return sorted(h, reverse=True) ``` O(N log K) — better than sorting all (O(N log N)) when K << N. ### Pattern: Merge K sorted lists ```python def merge_k_lists(lists): h = [] for i, lst in enumerate(lists): if lst: heapq.heappush(h, (lst[0], i, 0)) result = [] while h: val, list_idx, elem_idx = heapq.heappop(h) result.append(val) if elem_idx + 1 < len(lists[list_idx]): next_val = lists[list_idx][elem_idx + 1] heapq.heappush(h, (next_val, list_idx, elem_idx + 1)) return result ``` Tuples sort element-wise; first element is the comparison key. ## BST vs Heap — when to use which | Need | Structure | |---|---| | Always-min OR always-max (one extreme) | Heap | | Both extremes / sorted iteration | BST (sorted set) | | Top K elements | Heap of size K | | Rank / order / Kth smallest at any time | BST | | Just "is X in the set?" | Hashset (O(1)) | ## Tie-breaking in heaps If your items aren't directly comparable (e.g., custom objects), use tuples: ```python heapq.heappush(h, (priority, tiebreaker, item)) ``` The `tiebreaker` (often an insertion counter) avoids comparing the items themselves when priorities tie. ## Common BST/heap mistakes 1. **Forgetting heapq is min-only.** Negate for max-heap. 2. **Pushing complex objects without a sort key.** Tuples solve this. 3. **Using BST when heap suffices.** Heap is simpler if you only need one extreme. 4. **Heap of size K mistake.** Use min-heap of size K to track top-K LARGEST (not max-heap). 5. **Treating sortedcontainers as standard library.** It's not in Python stdlib; verify before using in interview. ## Takeaway BST: sorted tree, O(log N) ops, in-order = sorted. Use for ordered queries. Heap: O(log N) push/pop, instant peek, only one extreme. Use for top-K and priority queues. `heapq` is min-heap; negate for max. Tuples for tie-breaking. Most "top K" / "stream of min" / "Di