ACompressed recap
🧾
An AVL tree is a BST whose every node has balance factor h(L) − h(R) in {−1, 0, +1}. After an insertion, the lowest unbalanced ancestor is fixed by one rotation (LL right, RR left) or two (LR, RL); rotations keep the sorted inorder. The sparsest AVL tree of height h has N(h) = N(h − 1) + N(h − 2) + 1 nodes, so the height stays O(log n).
BMerged rule card
4.6 Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
- 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).
CInterleaved GATE-style questions
Q1NAT1 markMin nodes
Minimum nodes in an AVL tree of height 3 (edges)?
Numerical answer: ________
Q2MCQ1 markCase
Inserting 10, 30, 20 into an empty AVL tree is which case?
- (A) RR
- (B) LL
- (C) LR
- (D) RL
Q3MCQ2 marksResult
After inserting 10, 30, 20 into an empty AVL tree, the root is:
- (A) 20
- (B) 30
- (C) depends
- (D) 10
Q4MSQ2 marksFacts
Which are true?
- (A) Rotations change the inorder.
- (B) A perfect binary search tree is an AVL tree.
- (C) An AVL tree is a BST.
- (D) Every AVL tree is complete.
Q5NAT2 marksSequence
Insert 1 … 7 in increasing order into an empty AVL tree. What is the final height (edges)?
Numerical answer: ________
Q6MCQ1 markBalance factor
A leaf’s balance factor is:
- (A) 1
- (B) 0
- (C) −1
- (D) undefined
Q7NAT2 marksMax height
What is the largest possible height (edges) of an AVL tree with 12 nodes?
Numerical answer: ________
Q8MCQ1 markCost
Search in an AVL tree with n nodes costs:
- (A) O(1)
- (B) O(n log n)
- (C) O(n)
- (D) O(log n)
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 71 mark
N(3) = 4 + 2 + 1 = 7.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q2 Answer: (D)1 mark
20 is in the left subtree of 10’s right child.
- (A) is wrong: The path bends.
- (B) is wrong: The tree leans right.
- (C) is wrong: Mirror image of this case.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q3 Answer: (A)2 marks
The RL fix lifts 20.
- (B) is wrong: 30 becomes the right child.
- (C) is wrong: Deterministic.
- (D) is wrong: 10 becomes the left child.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q4 Answer: (B) (C)2 marks
AVL trees need not be complete; rotations keep inorder.
- (A) is wrong: Inorder is preserved.
- (D) is wrong: Balanced ≠ complete.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q5 Answer: 22 marks
It becomes the perfect tree rooted at 4: 2.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q6 Answer: (B)1 mark
Both subtrees empty (height −1 each).
- (A) is wrong: Equal heights.
- (C) is wrong: Equal heights.
- (D) is wrong: It is 0.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q7 Answer: 42 marks
N(4) = 12 ≤ 12 < N(5) = 20: 4.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height
Q8 Answer: (D)1 mark
The height is logarithmic.
- (A) is wrong: Not constant.
- (B) is wrong: Too much.
- (C) is wrong: That is a skewed BST.
Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height