Trees: BST, AVL Trees & Binary Heaps

Binary Search Tree — A Dictionary in a Tree

Think of a BST like a "hot or cold" guessing game. You have a target number. At each step, the tree tells you "go left if smaller, go right if bigger."

BST Property: For every node: - Everything in the LEFT subtree < node's value - Everything in the RIGHT subtree > node's value

Insert 50, 30, 70, 20, 40, 60, 80:

          50
        /    \
      30      70
     /  \    /  \
    20  40  60  80

Searching for 60: - Start at 50. Is 60 > 50? Yes → go right to 70. - Is 60 < 70? Yes → go left to 60. - Found! Took 3 steps (height = 3).

BST Traversals

Inorder (Left, Root, Right) visits nodes in sorted order — this is the key property!

Inorder of above tree: 20, 30, 40, 50, 60, 70, 80  ← sorted!

Preorder (Root, Left, Right): 50, 30, 20, 40, 70, 60, 80 Postorder (Left, Right, Root): 20, 40, 30, 60, 80, 70, 50

BST Delete — The Three Cases

Case 1 — Leaf node (delete 20): just remove it.

Case 2 — One child (delete 30 if it had only right child 40): replace 30 with 40.

Case 3 — Two children (delete 50 in our tree): Find the inorder successor (smallest value in right subtree = 60). Replace 50 with 60, then delete 60 from its original position.

          60          ← 50 replaced by its inorder successor
        /    \
      30      70
     /  \       \
    20  40      80

The Problem with BST: Skewed Trees

If you insert sorted data into a BST:

Insert 10, 20, 30, 40, 50:

10
  \
  20
    \
    30
      \
      40
        \
        50

This is no better than a linked list! Height = n, so all operations are O(n), not O(log n).

Solution: AVL Trees — self-balancing BSTs.

AVL Tree — Always Balanced

An AVL tree maintains: at every node, |height(left subtree) − height(right subtree)| ≤ 1.

This is called the balance factor (BF). It must be -1, 0, or +1.

If inserting/deleting causes BF to become ±2, the tree rotates to fix itself.

The Four Rotations

Think of rotations like turning a mobile toy to rebalance it.

LL Imbalance → Right Rotation

Inserted 10 into this tree (imbalanced at 30):

Imbalanced:         After Right Rotation:
    30                   20
   /                    /  \
  20                  10    30
 /
10

RR Imbalance → Left Rotation (mirror of LL)

Imbalanced:         After Left Rotation:
10                       20
  \                    /    \
  20                  10    30
    \
    30

LR Imbalance → Left Rotation on child, then Right Rotation on root

Imbalanced:                 Step 1 (Left on 10):    Step 2 (Right on 30):
    30                          30                       20
   /                           /                        /  \
  10                          20                       10   30
    \                        /
    20                      10

RL Imbalance → Right Rotation on child, then Left Rotation on root (mirror of LR)

Binary Heap — A Complete Tree in an Array

A max-heap is a complete binary tree where every parent is ≥ its children.

Max-heap:           Stored as array (1-indexed):
     90             Index: 1   2   3   4   5   6
    /  \            Value: 90  80  70  40  60  50
   80   70
  / \ /
 40 60 50

Key formula (1-indexed): - Parent of node i: ⌊i/2⌋ - Left child of i: 2i - Right child of i: 2i + 1

So node at index 3 (value 70): parent = ⌊3/2⌋ = 1 (value 90). Left child = 6 (value 50).

Insert — Bubble Up

Insert 85 into the max-heap:

Step 1: Place 85 at the next empty position (index 7, bottom-right).
Array: [90, 80, 70, 40, 60, 50, 85]

Step 2: Compare with parent. 85 > 70 (its parent at index 3)? Yes → SWAP.
Array: [90, 80, 85, 40, 60, 50, 70]

Step 3: Compare 85 with parent (index 1 = 90). 85 > 90? No → STOP.
Done! 85 is at index 3.

Each step goes up one level: O(log n) in the worst case.

Extract Max — Bubble Down

Remove the max (root):

Step 1: Replace root with last element (50), remove last.
Array: [50, 80, 70, 40, 60]

Step 2: 50 < 80 (left child)? Yes. Swap with larger child (80).
Array: [80, 50, 70, 40, 60]

Step 3: 50 < 60 (right child)? Yes. Swap.
Array: [80, 60, 70, 40, 50]

Step 4: 50 is a leaf. Stop.
Max removed was 90.

Build-Heap is O(n) — Not O(n log n)!

To build a heap from n elements, call heapify-down on all non-leaf nodes from bottom to top.

Most nodes are near the bottom where heapify only takes O(1). The math works out to O(n) total:

Level 0 (root): 1 node × O(log n) = O(log n)
Level 1:        2 nodes × O(log n - 1)
...
Level log n:    n/2 nodes × O(1)  ← most nodes
Total:  O(n)  (geometric series, not O(n log n))

This is a classic GATE trap. Build-heap = O(n). Heap sort = O(n log n) (because you then extract n times).

Quick Check

Q1. Insert 15 into this BST: root=10, right child=20. Where does 15 go?

Answer: left child of 20. (15 > 10 → go right. 15 < 20 → go left.)

Q2. In a max-heap stored as array [100, 60, 80, 30, 50, 70, 40], what is at index 3?

Answer: 80. (index 1=100, 2=60, 3=80, 4=30, 5=50, 6=70, 7=40)

Q3. What is the time complexity to build a max-heap from n unsorted elements?

Answer: O(n) using Floyd's bottom-up heapify.

Key Points