Advanced Trees

class MinHeap {
    private int[] heap;   // Array to store heap elements
    private int size;     // Current number of elements
    
    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }
}

A heap is stored as a simple array - no pointers needed! We just track the array and current size. The "tree structure" is virtual, calculated using index formulas.

    // Index formulas - THE KEY to heap implementation!
    private int parent(int i)     { return (i - 1) / 2; }  // Parent index
    private int leftChild(int i)  { return 2 * i + 1; }    // Left child index
    private int rightChild(int i) { return 2 * i + 2; }    // Right child index

Memorize these! For any node at index i: parent = (i-1)/2, leftChild = 2*i+1, rightChild = 2*i+2. This lets us navigate the "tree" using just array indices. No pointers!

    // Helper to swap two elements
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    
    // Peek at minimum (always at root)
    public int peek() {
        return heap[0];  // Min is always at index 0
    }
}

swap() exchanges two elements - used heavily during bubble up/down. peek() returns the min in O(1) - it's always at index 0 (root)!

// Insert element - O(log n)
public void insert(int val) {
    // Step 1: Add at the END of array
    heap[size] = val;
    int current = size;
    size++;

First, simply add the new value at the end of the array. This maintains the complete tree shape (level-by-level filling).

    // Step 2: BUBBLE UP - swap with parent while smaller
    //         (maintain min-heap property)
    while (current > 0 && heap[current] < heap[parent(current)]) {
        swap(current, parent(current));  // Swap with parent
        current = parent(current);        // Move up to parent's position
    }
    // Element finds its correct position!
}

Bubble Up: If new element is smaller than parent, swap them! Keep swapping upward until heap property is restored (parent ≤ child) or we reach root. Max swaps = tree height = O(log n).

The new element (2) is added at the end, then "bubbles up" by swapping with 5 since 2 < 5. It stops when 2 > 1 (parent).

// Extract minimum element - O(log n)
public int extractMin() {
    int min = heap[0];           // Save the minimum (root)
    heap[0] = heap[size - 1];    // Move LAST element to root
    size--;
    
    heapify(0);  // Fix heap property from root
    
    return min;
}

Save the root (minimum), replace it with the last element (maintains complete tree), decrease size, then call heapify to restore order.

// Heapify (bubble down) - restore heap property
private void heapify(int i) {
    int smallest = i;
    int left = leftChild(i);
    int right = rightChild(i);
    
    // Find smallest among node and its children
    if (left < size && heap[left] < heap[smallest])
        smallest = left;
    
    if (right < size && heap[right] < heap[smallest])
        smallest = right;
    
    // If smallest is not the current node, swap and recurse
    if (smallest != i) {
        swap(i, smallest);
        heapify(smallest);  // Continue down the tree
    }
}

Heapify Down: Compare node with both children, find the smallest. If node isn't smallest, swap with the smallest child and recurse. Continues until node ≤ both children or reaches leaf.

After removing 1, the last element (5) goes to root. Then 5 "sinks down" by swapping with 2 (smaller child). Heap property restored!

// Java's built-in heap implementation
import java.util.*;

// MinHeap (default) - smallest element has highest priority
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(5);  // Add elements
minHeap.offer(2);
minHeap.offer(8);
minHeap.poll();    // Returns 2 (smallest)
minHeap.peek();    // Returns 5 (next smallest)

PriorityQueue is a MinHeap by default. Use offer() to add, poll() to remove min, peek() to view min without removing.

// MaxHeap - largest element has highest priority
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// OR: new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
maxHeap.poll();    // Returns 8 (largest)

For MaxHeap, use Collections.reverseOrder() or custom comparator (a, b) -> b - a. Now poll() returns largest element!

// ========== HEAP SORT - O(n log n) ==========
void heapSort(int[] arr) {
    int n = arr.length;
    
    // Step 1: Build max heap - O(n)
    // Start from last non-leaf node and heapify all
    for (int i = n / 2 - 1; i >= 0; i--)
        heapifyForSort(arr, n, i);
    
    // Step 2: Extract elements one by one - O(n log n)
    for (int i = n - 1; i > 0; i--) {
        // Move current root (max) to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        // Heapify reduced heap
        heapifyForSort(arr, i, 0);
    }
    // Array is now sorted in ascending order!
}

Heap Sort: 1) Build max-heap from array. 2) Repeatedly swap root (max) with last element, shrink heap, heapify. Each max goes to its correct position at the end!

class SegmentTree {
    private int[] tree;  // Stores the segment tree nodes
    private int n;       // Original array size
    
    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];  // 4n space is safe for all cases
        build(arr, 0, 0, n - 1);
    }
}

We allocate 4n space for the tree array (safe upper bound). The tree is built in the constructor by calling recursive build function.

    // Build segment tree recursively - O(n)
    // node = current tree index
    // start, end = range this node represents
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            // Leaf node: store array element
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            
            // Build left subtree: covers [start, mid]
            build(arr, leftChild, start, mid);
            
            // Build right subtree: covers [mid+1, end]
            build(arr, rightChild, mid + 1, end);
            
            // Internal node: aggregate of children (sum in this case)
            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }
}

Leaf nodes (start == end) store array elements. Internal nodes store the sum of their children. Each node covers a range [start, end].

// Tree structure for arr = [1, 3, 5, 7]
//              [0,3]=16
//             /        \
//        [0,1]=4      [2,3]=12
//        /    \        /    \
//     [0]=1  [1]=3  [2]=5  [3]=7

Root [0,3] stores sum of entire array (16). Each level divides ranges in half. Leaves store individual elements. This structure enables O(log n) queries!

// Public API: Get sum of range [L, R]
public int query(int L, int R) {
    return query(0, 0, n - 1, L, R);
}

Simple public method that calls the recursive helper. User just provides [L, R] range to query.

// Recursive helper
// node = current tree index
// [start, end] = range this node covers
// [L, R] = range we're querying
private int query(int node, int start, int end, int L, int R) {
    
    // Case 1: NO OVERLAP - query range doesn't intersect node range
    if (R < start || end < L) {
        return 0;  // Return identity for sum (would be MAX_VALUE for min)
    }
    
    // Case 2: COMPLETE OVERLAP - node range is fully inside query range
    if (L <= start && end <= R) {
        return tree[node];  // Return this node's precomputed value
    }

No Overlap: If [L,R] doesn't touch [start,end], return 0. Complete Overlap: If node's range is fully inside query range, return precomputed value directly!

    // Case 3: PARTIAL OVERLAP - need to check both children
    int mid = (start + end) / 2;
    int leftSum = query(2 * node + 1, start, mid, L, R);
    int rightSum = query(2 * node + 2, mid + 1, end, L, R);
    
    return leftSum + rightSum;
}

Partial Overlap: Range partially intersects both halves. Query both children and combine results. This is the recursive case.

Query [1,2] hits partial overlap at root → recurse both children. Left gives 3, right gives 5. Sum = 8. Only O(log n) nodes visited!

// Public API: Update element at index idx to val
public void update(int idx, int val) {
    update(0, 0, n - 1, idx, val);
}

Simple wrapper that calls recursive helper. User provides index and new value.

// Recursive helper
private void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Found the leaf node for this index
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        
        // Decide which child contains our index
        if (idx <= mid) {
            // Index is in left half
            update(2 * node + 1, start, mid, idx, val);
        } else {
            // Index is in right half
            update(2 * node + 2, mid + 1, end, idx, val);
        }

Navigate down the tree: if target index is in left half, go left; otherwise go right. When start == end, we've found the leaf - update it!

        // Recalculate this node from updated children
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

After recursion returns, recalculate this node's value from its children. This propagates the change up to all ancestors.

// Example Usage:
int[] arr = {1, 3, 5, 7, 9, 11};
SegmentTree st = new SegmentTree(arr);

st.query(1, 3);    // Sum of arr[1..3] = 3+5+7 = 15
st.update(2, 10);  // Change arr[2] from 5 to 10
st.query(1, 3);    // Now = 3+10+7 = 20

After update, subsequent queries automatically reflect the change. Both query and update are O(log n)!

class Trie {
    // Each node can have 26 children (a-z)
    class TrieNode {
        TrieNode[] children = new TrieNode[26];  // 26 letters
        boolean isEndOfWord = false;              // Marks complete word
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();  // Empty root node
    }
}

Each node has 26 children (one for each letter a-z) and an isEndOfWord flag to mark complete words. Root is always empty.

    // Insert a word - O(m) where m = word length
    public void insert(String word) {
        TrieNode node = root;
        
        for (char c : word.toCharArray()) {
            int index = c - 'a';  // 'a'→0, 'b'→1, ... 'z'→25
            
            // Create child node if it doesn't exist
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            
            // Move to child
            node = node.children[index];
        }
        
        // Mark last node as end of word
        node.isEndOfWord = true;
    }
}

For each character: calculate index (c - 'a'), create child if needed, move down. Finally mark isEndOfWord = true.

Words sharing prefix ("app") reuse the same path. The ★ marks where complete words end. "app" and "apple" share a→p→p, then diverge.

// Helper: Navigate trie following a string
private TrieNode searchNode(String word) {
    TrieNode node = root;
    
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        
        // Character path doesn't exist → word not in trie
        if (node.children[index] == null) {
            return null;
        }
        
        node = node.children[index];
    }
    
    return node;  // Return the node at end of path
}

Navigates the trie following the string. Returns null if path doesn't exist, otherwise returns the final node.

// Search for EXACT word - O(m)
public boolean search(String word) {
    TrieNode node = searchNode(word);
    // Must exist AND be marked as end of word
    return node != null && node.isEndOfWord;
}

search() returns true only if path exists AND node has isEndOfWord = true. "ap" exists as path but isn't a complete word!

// Check if ANY word starts with prefix - O(m)
public boolean startsWith(String prefix) {
    // Just check if path exists - don't need isEndOfWord
    return searchNode(prefix) != null;
}

startsWith() just checks if path exists - doesn't care about isEndOfWord. "ap" returns true because it's a prefix of "app"!

// Examples after inserting "app", "apple", "application":
//
// search("app")      → true  (path exists + isEndOfWord)
// search("ap")       → false (path exists, but NOT isEndOfWord)
// search("apx")      → false (path doesn't exist)
// startsWith("app")  → true  (path exists)
// startsWith("ap")   → true  (path exists)
// startsWith("apx")  → false (path doesn't exist)

Key difference: "ap" fails search (not a word) but passes startsWith (is a prefix). "apx" fails both (path doesn't exist at all).

// Count all words that start with given prefix
public int countWordsWithPrefix(String prefix) {
    TrieNode node = searchNode(prefix);
    
    if (node == null) return 0;  // Prefix doesn't exist
    
    return countWords(node);  // Count words in subtree
}

First navigate to the prefix node. If it doesn't exist, return 0. Otherwise count all words in that subtree.

// Recursively count words in subtree
private int countWords(TrieNode node) {
    // Count this node if it's end of word
    int count = node.isEndOfWord ? 1 : 0;
    
    // Add counts from all children
    for (TrieNode child : node.children) {
        if (child != null) {
            count += countWords(child);
        }
    }
    
    return count;
}

DFS through subtree: count current node if it's end of word, then recursively count all children.

// ========== USAGE EXAMPLE ==========
Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
trie.insert("banana");

trie.search("app");                  // true  - exact word exists
trie.search("ap");                   // false - not a complete word
trie.startsWith("app");              // true  - prefix exists
trie.countWordsWithPrefix("app");    // 3 (app, apple, application)
trie.countWordsWithPrefix("ban");    // 1 (banana)

"app" prefix matches 3 words (app, apple, application). Perfect for autocomplete suggestions!

import java.util.*;

// TreeSet - Sorted Set backed by Red-Black Tree
TreeSet set = new TreeSet<>();
set.add(5);
set.add(2);
set.add(8);
set.add(1);
// Set is ALWAYS sorted: {1, 2, 5, 8}

🎯 What's happening here? TreeSet is like a magical container that automatically keeps your numbers sorted!

Key Points:
• When you add elements in any order (5, 2, 8, 1), TreeSet automatically arranges them as {1, 2, 5, 8}
• No duplicates allowed - adding 5 twice still keeps only one 5
• Uses a Red-Black Tree internally (self-balancing BST)
• All operations (add, remove, contains) take O(log n) time - much faster than sorting an array!

// ========== Navigation Methods ==========
set.first();         // 1 (smallest element)
set.last();          // 8 (largest element)

// Floor/Ceiling - find nearest element
set.floor(3);        // 2 (largest element ≤ 3)
set.ceiling(3);      // 5 (smallest element ≥ 3)

// Lower/Higher - strictly less/greater
set.lower(5);        // 2 (largest element < 5)
set.higher(5);       // 8 (smallest element > 5)

🔍 Understanding Navigation Methods: These are super useful for finding "nearest" elements!

How to remember:
• floor(3) = "What's the largest number ≤ 3?" → Answer: 2 (it's on the "floor" below or equal)
• ceiling(3) = "What's the smallest number ≥ 3?" → Answer: 5 (it's on the "ceiling" above or equal)
• lower(5) = "Strictly less than 5" → 2 (doesn't include 5 itself)
• higher(5) = "Strictly greater than 5" → 8 (doesn't include 5 itself)
All these operations are O(log n) - extremely efficient for finding nearby values!

// ========== Subset Views ==========
set.headSet(5);      // {1, 2} - all elements < 5
set.tailSet(5);      // {5, 8} - all elements ≥ 5
set.subSet(2, 8);    // {2, 5} - elements in [2, 8)

// ========== Common Patterns ==========
// Find Kth smallest (sorted iteration)
int k = 2;
Iterator it = set.iterator();
for (int i = 1; i < k; i++) it.next();
int kthSmallest = it.next();  // 2nd smallest = 2

📊 Subset Views Explained: Think of these as "windows" into your sorted data!

Breaking it down:
• headSet(5) = "Give me everything BEFORE 5" → {1, 2} (head of the list)
• tailSet(5) = "Give me 5 and everything AFTER" → {5, 8} (tail of the list)
• subSet(2, 8) = "Give me elements from 2 (inclusive) to 8 (exclusive)" → {2, 5}
⚠️ Important: These views are "live" - if you modify the original set, the view changes too!
Pattern: To find Kth smallest, just iterate K times - elements come out in sorted order automatically.

// TreeMap - Sorted Map backed by Red-Black Tree
TreeMap map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");
// Map is sorted by KEYS: {1=one, 2=two, 3=three}

🗺️ What's a TreeMap? It's like a dictionary that keeps entries sorted by their "words" (keys)!

Key Concepts:
• Stores key-value pairs like HashMap, but keys are ALWAYS in sorted order
• When you add {3="three", 1="one", 2="two"}, it automatically becomes {1="one", 2="two", 3="three"}
• Sorting is based on KEYS only (not values) - values can be in any order
• Uses Red-Black Tree internally, so put/get/remove are all O(log n)
Trade-off: Slightly slower than HashMap (O(log n) vs O(1)), but you get sorted keys!

// ========== Key Navigation ==========
map.firstKey();       // 1 (smallest key)
map.lastKey();        // 3 (largest key)
map.floorKey(2);      // 2 (largest key ≤ 2)
map.ceilingKey(2);    // 2 (smallest key ≥ 2)
map.lowerKey(2);      // 1 (largest key < 2)
map.higherKey(2);     // 3 (smallest key > 2)

🔑 Key Navigation Methods: Find the nearest keys without knowing exact values!

How they work:
• firstKey()/lastKey() - Get the smallest/largest key instantly
• floorKey(2) - "What's the largest key ≤ 2?" → 2 itself exists, so returns 2
• ceilingKey(2) - "What's the smallest key ≥ 2?" → 2 exists, so returns 2
• lowerKey(2)/higherKey(2) - Strictly less/greater → 1 and 3
💡 Use Case: Perfect for "find nearest available time slot" or "find closest price point" problems!

// ========== Entry Navigation ==========
map.firstEntry();     // 1=one (smallest entry)
map.lastEntry();      // 3=three (largest entry)
map.pollFirstEntry(); // Remove and return smallest
map.pollLastEntry();  // Remove and return largest

📋 Entry Navigation: Get both key AND value together!

Understanding the difference:
• firstEntry() returns the entire entry (1="one") - you get both key and value
• firstKey() returns just the key (1) - no value included
• pollFirstEntry() = "Give me the smallest entry AND remove it" - like a priority queue!
• pollLastEntry() = "Give me the largest entry AND remove it"
💡 Pattern: Use poll* methods to process elements in sorted order (like merging K sorted lists)!

// ========== Common Interview Pattern ==========
// Maintain sorted frequency count
TreeMap freqMap = new TreeMap<>();
freqMap.merge(key, 1, Integer::sum);  // Increment count

// All operations are O(log n)!

🎯 Interview Pattern - Frequency Counting: A must-know technique!

The merge() method explained:
• merge(key, 1, Integer::sum) means: "If key exists, add 1 to its value. If not, set it to 1"
• This is cleaner than: map.put(key, map.getOrDefault(key, 0) + 1)
• TreeMap keeps counts sorted by key - useful for finding min/max frequency
💼 Real Interview Problems:
• Calendar scheduling (find overlapping meetings)
• Interval merging (sorted start/end times)
• Skyline problem, meeting rooms II