Advanced Trees

Back to DSA & Algorithms/00 - Roadmap Overview | See also 07 - Trees

---

Self-Balancing BSTs (Know the Concepts, Not the Implementation)

FAANG interviews won't ask you to implement AVL or Red-Black trees. But they will expect you to:

1. Know what they are and why they exist
2. Know when to use TreeMap/TreeSet (Java) or SortedMap (JS via libraries)
3. Understand O(log n) guarantees

---

AVL Tree

What it is

A BST where for every node, the height difference between left and right subtrees is at most 1. Named after inventors Adelson-Velsky and Landis.

Why it exists

A regular BST can degenerate into a linked list (insert sorted data: 1→2→3→4→5). This makes search O(n) instead of O(log n). AVL trees rebalance after every insertion/deletion to keep height = O(log n).

Balance Factor

Balance Factor = height(left subtree) - height(right subtree)
Valid values: -1, 0, +1
If outside this range → rotation needed

The Four Rotations

1. LEFT-LEFT (LL) → Single Right Rotation

        30                  20
       /                   /  \
      20         →       10    30
     /
    10

2. RIGHT-RIGHT (RR) → Single Left Rotation

    10                      20
      \                    /  \
       20        →       10    30
        \
         30

3. LEFT-RIGHT (LR) → Left Rotation on child, then Right Rotation

        30                  30                  25
       /                   /                   /  \
      20         →       25         →        20    30
        \               /
         25            20

4. RIGHT-LEFT (RL) → Right Rotation on child, then Left Rotation

    10                  10                      15
      \                   \                    /  \
       20        →        15        →        10    20
      /                     \
     15                      20

Complexity

When to Mention AVL in Interviews

• "I'd use a balanced BST (like TreeMap in Java) for O(log n) sorted operations"
• "This requires maintaining sorted order with O(log n) insert/delete — a self-balancing BST"
• When you need: sorted iteration, floor/ceiling queries, rank queries

---

Red-Black Tree

What it is

A self-balancing BST with colored nodes (red or black) and specific rules that keep the tree approximately balanced. Less strictly balanced than AVL but faster for insertions/deletions.

The Rules (for awareness)

1. Every node is red or black
2. Root is always black
3. No two consecutive red nodes (red node's children must be black)
4. Every path from root to null has the same number of black nodes

Why It Matters for You

Java's TreeMap, TreeSet, and PriorityQueue (sorted variants) use Red-Black trees internally.

java
// This is a Red-Black tree under the hood:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(5, "five");
map.put(3, "three");
map.put(8, "eight");

map.firstKey();         // 3    — O(log n)
map.lastKey();          // 8    — O(log n)
map.floorKey(4);        // 3    — largest key ≤ 4
map.ceilingKey(4);      // 5    — smallest key ≥ 4
map.subMap(3, 8);       // keys in [3, 8) — O(log n + k)

TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.lower(5);           // 3    — largest element < 5
set.higher(5);          // 8    — smallest element > 5

AVL vs Red-Black

---

Segment Tree

What it is

A tree that stores information about ranges (segments) of an array. Supports:

• Range query (sum/min/max of elements from index L to R): O(log n)
• Point update (change one element): O(log n)

When to use it

• "Range sum query with updates" (array changes over time)
• "Range minimum/maximum query"
• Regular prefix sum only works if the array doesn't change

The Mental Model

Each node represents a segment of the array. Leaves = individual elements. Internal nodes = aggregation (sum/min/max) of their children's segments.

Array: [1, 3, 5, 7, 9, 11]

                [36]              sum of [0..5]
              /      \
          [9]          [27]       sum of [0..2] and [3..5]
         /   \        /    \
       [4]   [5]   [16]   [11]   sum of [0..1],[2..2],[3..4],[5..5]
      / \         /    \
    [1] [3]     [7]   [9]

Query sum(1, 4):  3 + 5 + 7 + 9 = 24
Update index 2 to 10: change leaf, update parents up to root

Implementation (Java)

java
class SegmentTree {
    int[] tree;
    int n;

    SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];  // 4x size is safe upper bound
        build(nums, 1, 0, n - 1);
    }

    // Build the tree recursively
    void build(int[] nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];  // Leaf node
            return;
        }
        int mid = (start + end) / 2;
        build(nums, 2 * node, start, mid);       // Left child = 2*node
        build(nums, 2 * node + 1, mid + 1, end); // Right child = 2*node+1
        tree[node] = tree[2 * node] + tree[2 * node + 1]; // Merge
    }

    // Point update: set nums[idx] = val
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1]; // Re-merge
    }

    // Range query: sum of elements from l to r
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;       // No overlap
        if (l <= start && end <= r) return tree[node]; // Full overlap
        int mid = (start + end) / 2;               // Partial overlap
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
}

Complexity

Problems

• 307. Range Sum Query - Mutable - Medium
• 315. Count of Smaller Numbers After Self - Hard

---

Binary Indexed Tree (Fenwick Tree)

What it is

A simpler alternative to Segment Tree for prefix sum queries with point updates. Uses clever bit manipulation to store partial sums.

When to Use Fenwick vs Segment Tree

Use Fenwick when you only need sum queries. Use Segment Tree when you need min/max or more complex operations.

Implementation (Java)

java
class BIT {
    int[] tree;
    int n;

    BIT(int n) {
        this.n = n;
        tree = new int[n + 1]; // 1-indexed
    }

    // Add val to index i (1-indexed)
    void update(int i, int delta) {
        for (; i <= n; i += i & (-i)) // Move to next responsible node
            tree[i] += delta;
    }

    // Prefix sum from 1 to i
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))  // Move to parent
            sum += tree[i];
        return sum;
    }

    // Range sum from l to r
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

// The magic: i & (-i) gives the lowest set bit
// This determines the "responsibility range" of each index
//
// Index  Binary  i & (-i)  Responsible for
//   1     0001      1       [1, 1]
//   2     0010      2       [1, 2]
//   3     0011      1       [3, 3]
//   4     0100      4       [1, 4]
//   5     0101      1       [5, 5]
//   6     0110      2       [5, 6]
//   7     0111      1       [7, 7]
//   8     1000      8       [1, 8]

Problems

• 307. Range Sum Query - Mutable - Medium
• 493. Reverse Pairs - Hard

---

N-ary Tree

What it is

A tree where each node can have any number of children (not just 2).

java
class Node {
    int val;
    List<Node> children;
}

Traversal is the Same Concept, Just Loop Over Children

java
// DFS (preorder)
void dfs(Node node) {
    if (node == null) return;
    process(node.val);
    for (Node child : node.children) {
        dfs(child);
    }
}

// BFS (level order) — identical to binary tree BFS
List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            level.add(node.val);
            for (Node child : node.children) {
                queue.offer(child);
            }
        }
        result.add(level);
    }
    return result;
}

Problems

• 429. N-ary Tree Level Order Traversal - Medium
• 589. N-ary Tree Preorder Traversal - Easy
• 590. N-ary Tree Postorder Traversal - Easy

---

When to Mention Each in Interviews

---

Decision Guide

Need sorted insert/delete/search in O(log n)?
  └── Use TreeMap/TreeSet (Red-Black tree internally)

Need floor/ceiling/range queries?
  └── TreeMap methods: floorKey(), ceilingKey(), subMap()

Range sum + point updates?
  └── Fenwick Tree (simpler) or Segment Tree

Range min/max + updates?
  └── Segment Tree (Fenwick can't do this)

Static range sum (no updates)?
  └── Prefix sum array (simplest, O(1) query)