All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Balanced BSTs (AVL, Red-Black — Conceptual)

Balanced BSTs (AVL, Red-Black — Conceptual)

0/12 in this phase0/57 across the roadmap

📖 Concept

Self-balancing BSTs guarantee O(log n) operations by maintaining tree height ≈ log n. You likely won't implement them from scratch in interviews, but understanding them is crucial.

AVL Tree:

  • Balance factor = height(left) - height(right), must be {-1, 0, 1}
  • After insert/delete, if unbalanced: perform rotations
  • Rotations: Left, Right, Left-Right, Right-Left
  • Strictly balanced → faster lookups than Red-Black
  • More rotations per operation → slower insertions

Red-Black Tree:

  • Each node is Red or Black with rules:
    1. Root is black
    2. No two adjacent red nodes
    3. Every path from root to leaf has same number of black nodes
  • Less strictly balanced than AVL → fewer rotations
  • Used in: Java TreeMap, C++ std::map, Linux kernel

AVL vs Red-Black vs Skip List:

Feature AVL Red-Black Skip List
Height 1.44 log n 2 log n ~log n
Lookup Faster Slightly slower Same
Insert/Delete More rotations Fewer rotations Simpler
Implementation Complex Very complex Moderate
Used in Databases Language STL Redis, LevelDB

In interviews: Know WHAT they do, WHY they exist, and WHEN to mention them. You'll almost never implement one from scratch.

🏠 Real-world analogy: An AVL tree is like a very strict manager who rebalances the team immediately when one side gets too heavy. A Red-Black tree is a more relaxed manager who allows a bit of imbalance but keeps things within bounds.

💻 Code Example

codeTap to expand ⛶
1// AVL TREE — Conceptual implementation (simplified)
2class AVLNode {
3  constructor(val) {
4    this.val = val;
5    this.left = null;
6    this.right = null;
7    this.height = 1;
8  }
9}
10

11class AVLTree {
12  constructor() { this.root = null; }
13

14  height(node) { return node ? node.height : 0; }
15  balanceFactor(node) { return this.height(node.left) - this.height(node.right); }
16  updateHeight(node) { node.height = 1 + Math.max(this.height(node.left), this.height(node.right)); }
17

18  // RIGHT ROTATION
19  rotateRight(y) {
20    const x = y.left;
21    y.left = x.right;
22    x.right = y;
23    this.updateHeight(y);
24    this.updateHeight(x);
25    return x;
26  }
27

28  // LEFT ROTATION
29  rotateLeft(x) {
30    const y = x.right;
31    x.right = y.left;
32    y.left = x;
33    this.updateHeight(x);
34    this.updateHeight(y);
35    return y;
36  }
37

38  insert(val) { this.root = this._insert(this.root, val); }
39

40  _insert(node, val) {
41    if (!node) return new AVLNode(val);
42    if (val < node.val) node.left = this._insert(node.left, val);
43    else if (val > node.val) node.right = this._insert(node.right, val);
44    else return node; // No duplicates
45

46    this.updateHeight(node);
47    const bf = this.balanceFactor(node);
48

49    // Left-Left → Right rotate
50    if (bf > 1 && val < node.left.val) return this.rotateRight(node);
51    // Right-Right → Left rotate
52    if (bf < -1 && val > node.right.val) return this.rotateLeft(node);
53    // Left-Right → Left rotate left child, then right rotate
54    if (bf > 1 && val > node.left.val) {
55      node.left = this.rotateLeft(node.left);
56      return this.rotateRight(node);
57    }
58    // Right-Left → Right rotate right child, then left rotate
59    if (bf < -1 && val < node.right.val) {
60      node.right = this.rotateRight(node.right);
61      return this.rotateLeft(node);
62    }
63    return node;
64  }
65}
66

67// When you'd mention balanced BSTs in interviews:
68// "I'd use a balanced BST here for O(log n) insert + ordered iteration"
69// "JavaScript doesn't have a built-in TreeMap, but we could use a sorted array
70//  with binary search, or implement a skip list"
71// "In production, I'd use a library like 'bintrees' for a Red-Black Tree"

🏋️ Practice Exercise

Practice Problems:

  1. Understand and draw all 4 AVL rotation cases (LL, RR, LR, RL)
  2. Insert elements 1-7 into an AVL tree and show each rotation
  3. Explain why Red-Black trees are preferred in language STLs
  4. Implement basic AVL insert with rotations
  5. Given a sequence of operations, what does the AVL tree look like after each?
  6. Compare the height guarantees of AVL vs Red-Black trees
  7. When would you use a balanced BST vs a hash map? (ordering matters!)
  8. Implement an order-statistics tree (find kth element in O(log n))
  9. Design a data structure that supports insert, delete, and getMedian all in O(log n)
  10. Explain the trade-offs between AVL, Red-Black, B-Tree, and Skip List

⚠️ Common Mistakes

  • Trying to implement AVL/Red-Black in an interview from scratch — just explain when you'd use them

  • Not knowing that JavaScript has no built-in ordered set/map — this affects DS selection in interviews

  • Confusing BST balance with heap property — they're completely different invariants

  • Using a balanced BST when a hash map suffices — only use BST when you need ordering

  • Not mentioning balanced BSTs when appropriate — 'I'd use a sorted structure for O(log n) operations'

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Balanced BSTs (AVL, Red-Black — Conceptual)

← PreviousBinary Indexed Tree (Fenwick Tree)Next →Bloom Filters & Probabilistic Data Structures