Binary Search Trees and Heaps

# CHAPTER 11

Binary Search Trees and Heaps #

1. Chapter Introduction #

2. The Binary Search Tree (BST) Property #

1. 1. All nodes in the Left Subtree must be strictly LESS than the parent node's value.

1. 2. All nodes in the Right Subtree must be strictly GREATER than the parent node's value.

*The Superpower:* If you are looking for 7, and you are standing at root 10, you know 100% that 7 CANNOT be in the right subtree. You discard the entire right half of the tree instantly. Search, Insert, and Delete are O(log N) Time.

3. Pattern 1: Validating a BST #

def isValidBST(root):
    def validate(node, low, high):
        if not node:
            return True # Empty nodes are valid
            
        # The node's value must stay within the strict boundaries
        if not (low < node.val < high):
            return False
            
        # Left child: Upper bound becomes the current node's value
        # Right child: Lower bound becomes the current node's value
        return (validate(node.left, low, node.val) and 
               validate(node.right, node.val, high))
               
    # Start with absolute infinity as bounds
    return validate(root, float(&#039;-inf'), float('inf'))

4. The In-Order Traversal Secret #

5. What is a Heap? #

• Min-Heap: The parent node is always smaller than or equal to its children. (The absolute smallest number in the entire tree is always sitting at the very top, the Root).

• Max-Heap: The parent is always larger than its children. (The biggest number is at the top).

Heap Operations:

• Peek Minimum: O(1) Time. (Just look at the root).

• Insert: O(log N) Time. (Add to bottom, "bubble up").

• Extract Minimum: O(log N) Time. (Remove root, replace with bottom, "bubble down").

6. The Priority Queue (Heap Implementation) #

• Python: import heapq (Min-Heap by default).

• Java: PriorityQueue<Integer> pq = new PriorityQueue<>();

7. Pattern 2: The "Top K" Elements (Heap) #

1. 1. Maintain a Min-Heap of size K.

1. 2. Iterate through the array, pushing elements into the Heap.

1. 3. If the Heap size exceeds K, pop() the minimum element.

1. 4. At the end, the Heap will contain exactly the K largest elements. Because it's a Min-Heap, the smallest of those K largest elements (which is the exact Kth largest overall) will be sitting at the very top of the heap!

import heapq

def findKthLargest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap) # Kick out the smallest number
            
    return min_heap[0] # The Kth largest is at the top
# Time: O(N log K), Space: O(K)

8. Mini Project: Merge K Sorted Lists #

1. 1. Create a Min-Heap.

1. 2. Put the head node of all K lists into the heap.

1. 3. While the heap is not empty:

1. 4. Pop the smallest node. Append it to your final result list.

1. 5. If that popped node has a next node, push node.next into the heap.

9. Common Mistakes #

• Assuming Python has a Max-Heap: Python's heapq is strictly a Min-Heap. If you need a Max-Heap in Python, you must multiply all numbers by -1 before pushing them in, and multiply by -1 when popping them out.

• BST Unbalanced Nightmare: In the worst-case scenario, if you insert sorted numbers [1,2,3,4] into a basic BST, it just becomes a straight line (a Linked List). Search time degrades from O(log N) to O(N). Production databases use self-balancing trees (AVL or Red-Black trees) to prevent this.

10. Best Practices #

• Use the standard library: Do not attempt to implement the bubble_up array logic for a Heap in an interview. Use PriorityQueue (Java) or heapq (Python).

11. Exercises #

1. 1. What does the array representation of an In-Order traversal look like for a valid BST?

1. 2. If you push [5, 2, 8, 1] into a Min-Heap, what number is at the root?

12. MCQs #

14. Interview Questions #

• Q: "Design a class to find the Kth largest element in a stream. The class will be instantiated with k and an initial array, and requires an add(val) method that returns the current Kth largest element after every insertion." (LeetCode 703).

15. FAQs #

• Q: Are Heaps implemented as Trees or Arrays?

16. Summary #

17. Next Chapter Recommendation #