Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many insertion orders of {1, …, 7} give the perfectly balanced BST? from Lesson 4.5.4
• What is the worst-case height of a BST with n keys, and when does it happen? from Lesson 4.5.2
• What is the maximum number of nodes in a binary tree of height h (edges)? from Lesson 4.2.2

1 · The Hook

🎣

A tightrope walker constantly makes small corrections to stay balanced instead of waiting to fall. An AVL tree (named after Adelson-Velsky and Landis) is a BST that checks its balance after every insertion and fixes it with a small local rearrangement, so its height never exceeds about 1.44 log₂ n.

2 · Predict First

🤔

Insert 1, 2, 3 into an empty BST: you get a chain. What single rearrangement makes it balanced while keeping the BST order? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Lift 2 to the root with 1 on its left and 3 on its right: a left rotation at 1. Inorder stays 1 2 3.

Balance factor

For each node: balance factor = height(left subtree) − height(right subtree). An AVL tree requires every node’s balance factor to be −1, 0 or +1. After an insertion, only nodes on the path from the new leaf to the root can become unbalanced (±2).

Rotations

Fix the lowest unbalanced node z by a rotation chosen from where the new key went (inside z’s subtrees):

A rotation changes O(1) pointers, keeps the inorder (BST order) and restores the subtree’s height, so one fix per insertion suffices. Insert, delete and search are all O(log n).

Worked sequence

Inserting 10, 20, 30, 25, 28, 27, 5 (computed): RR at 10: left rotation; LR at 30: left rotation at 25, then right rotation at 30; RL at 20: right rotation at 28, then left rotation at 20; LL at 20: right rotation. Final preorder: 25 10 5 20 28 27 30.

Minimum nodes for a given height

The sparsest AVL tree of height h has a root, one subtree of height h − 1 and one of height h − 2, each as sparse as possible:

N(0) = 1, N(1) = 2, N(h) = N(h − 1) + N(h − 2) + 1

So an AVL tree with n nodes has height at most about 1.44 log₂ n. (With the nodes convention, N(1) = 1, N(2) = 2, … shift by one.) This lesson is low weight in GATE: know the definition, the four cases and N(h).

4 · Visual

AVL tree after inserting 10 20 30 25 28 27 5: balance factors (left − right height) under each node are all −1, 0 or +1.

The same keys in a plain BST: height 5.

Right rotation at z (LL case):           Left rotation at z (RR case):

        z                y                   z                    y
       / \             /   \                / \                 /   \
      y   T4    ->    x     z              T1  y       ->      z     x
     / \             / \   / \                / \             / \   / \
    x   T3          T1 T2 T3 T4              T2  x           T1 T2 T3 T4
   / \                                          / \
  T1  T2                                       T3  T4

inorder before = inorder after: T1 x T2 y T3 z T4

A rotation re-hangs three nodes and their subtrees without changing the sorted order.

5 · Worked Examples

Example 1 Easy

Insert 1, 2, 3, 4, 5, 6, 7 into an empty AVL tree. What is the final preorder and height?

Solution

Rotations keep it balanced: preorder 4 2 1 3 6 5 7, height 2 (a plain BST would have height 6).

Example 2 Medium

What is the minimum number of nodes in an AVL tree of height 5 (edges)? Of height 4?

Solution

N(5) = 20, N(4) = 12.

Example 3 GATE

Insert 10, 20, 30, 25, 28, 27, 5 into an empty AVL tree. Which rotations occur, and what is the root at the end?

Solution

RR at 10: left rotation; LR at 30: left rotation at 25, then right rotation at 30; RL at 20: right rotation at 28, then left rotation at 20; LL at 20: right rotation. The root ends as 25.

6 · GATE Traps

⚠️

• Balance factor is height(left) − height(right); allowed values −1, 0, +1.
• Fix the lowest unbalanced ancestor of the new node.
• LR and RL need two rotations; LL and RR one.
• Rotations preserve the inorder sequence.
• Min nodes N(h) = N(h − 1) + N(h − 2) + 1 depends on the height convention; check N(0).

8 · Memory Hook

🧠

“Lean too far, rotate back.” Straight lean (LL/RR): one rotation; bent lean (LR/RL): straighten first, then rotate.

9 · Connect the Dots

Phase 4 is complete: trees, binary trees, traversals, BSTs and their balanced version. BSTs keep every key in order. Many problems only need the largest (or smallest) item quickly, like an emergency room that always treats the most critical patient next. Phase 5 answers: which simpler tree, stored in an array, gives the maximum instantly?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markBalance factor

A node whose left subtree has height 3 and right subtree height 1 has balance factor:

• (A) 2
• (B) −2
• (C) 1
• (D) 4

Q2MCQ1 markRotation

Inserting 30, 20, 10 into an empty AVL tree needs:

• (A) no rotation
• (B) a left-right double rotation
• (C) a single right rotation
• (D) a single left rotation

Q3NAT2 marksMin nodes

Minimum number of nodes in an AVL tree of height 6 (edges, single node height 0)?

Numerical answer: ________

Q4MCQ2 marksDouble rotation

Inserting 30, 10, 20 into an empty AVL tree triggers which case?

• (A) RR
• (B) LL
• (C) RL
• (D) LR

Q5MSQ1 markFacts

Which are true for AVL trees?

• (A) Search is O(log n).
• (B) Every node has balance factor 0.
• (C) Rotations preserve the inorder sequence.
• (D) The height is at most about 1.44 log₂ n.

11 · Rule Card

• AVL: every node’s balance factor h(L) − h(R) ∈ {−1, 0, +1}.
• LL → right rotation; RR → left rotation; LR → left then right; RL → right then left.
• Rotations keep inorder, fix height, cost O(1).
• Min nodes: N(0) = 1, N(1) = 2, N(h) = N(h−1) + N(h−2) + 1 (1, 2, 4, 7, 12, 20, 33).
• Height ≈ ≤ 1.44 log₂ n; all operations O(log n).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

AVL treebalance factorsingle rotation (LL, RR)double rotation (LR, RL)minimum nodes N(h)

13 · Answer Vault