AVL Tree MCQs: 12 Solved Balancing and Rotation Questions

AVL questions become error-prone when you mix up a node's balance factor with the rotation direction, or rotate before finding the first unbalanced ancestor. AVL balancing starts with the balance rule, then moves through LL, RR, LR and RL cases, insertion traces, height bounds and complexity. Choose an option and sketch the affected three-node subtree before reading each explanation.

You can practise over 50 AVL Trees & Balancing questions in Coding & DSA. Questions 6 and 10 are not yet linked to their own practice pages, so open them from the AVL Trees & Balancing question hub.

Balance factors and one worked LR rotation before the MCQs

For a node v, BF(v) = height(left(v)) - height(right(v)). An AVL node is valid only when its balance factor is -1, 0 or +1. After insertion, walk towards the root and repair the first ancestor for which |BF| = 2.

Insert 30, 10, 20. After 20 is inserted, node 30 has left height 1, empty-right height -1, and BF(30) = 1 - (-1) = +2. Node 10 has BF(10) = -1, so this is LR. Left-rotate at 10. Now 30 has left child 20, whose left child is 10. Right-rotate at 30. The final root is 20, with children 10 and 30. All three balance factors are 0. If ordinary insertion is unclear, revise Binary Trees and Binary Search Trees first.

AVL Tree MCQs 1-2: the invariant and the rebalance trigger

Question 1

What is balance factor of an AVL tree?

• A. |h(TL)| ≤ 1

• B. |h(TR)| ≤ 1

• C. h(TL) – h(TR)| ≤ 1

• D. |h(TL) + h(TR)| ≤ 1

Answer: C. h(TL) – h(TR)| ≤ 1. The complete definition is BF = h(TL) - h(TR), and the AVL condition is |BF| <= 1. A and B restrict one subtree alone. D adds the heights instead of comparing them. Option C is the intended answer even though its opening absolute-value bar is missing from the printed choice. See it solved.

Question 2

In an AVL tree, at what condition the balancing is to be done

• A. The Height factor is greater than 2 or less than -2

• B. The Height factor is greater than 1 or less than -1

• C. The Height factor is greater than 2 or less than -1

• D. The Height factor is greater than 1 or less than -2

Answer: B. The Height factor is greater than 1 or less than -1. Precisely, rebalance when BF > 1 or BF < -1, equivalently |BF| > 1. A waits too long. C and D use asymmetric thresholds even though left-heavy and right-heavy violations are mirror cases. See it solved.

AVL Tree MCQs 3-4: single versus double rotations

Question 3

Which rotations in AVL trees are known as single rotations?

• A. LL and RR

• B. LL and LR

• C. RR and RL

• D. LR and RL

Answer: A. LL and RR. These are outside cases. LL needs one right rotation at the unbalanced node, while RR needs one left rotation. The case name describes the heavy path, not the physical rotation direction. LR and RL are inside cases and need two steps. See it solved.

Question 4

Which rotations in an AVL tree is known as double rotation?

• A. LL and RR

• B. LR and LL

• C. RL and RR

• D. LR and RL

Answer: D. LR and RL. For LR, left-rotate the left child and then right-rotate the unbalanced node, exactly as in the 30, 10, 20 trace. For RL, right-rotate the right child and then left-rotate the node. See it solved.

AVL Tree MCQs 5-7: count rotations through full insertion traces

Question 5

The number of rotations required to insert a sequence of elements 9,6,5,8,7,10 into an empty AVL tree is?

• A. 0

• B. 1

• C. 2

• D. 3

Answer: D. 3. Inserting 9, 6, 5 causes LL at 9, so right-rotate 9. The 8 needs no repair. Inserting 7 causes LL at 9, so right-rotate 9 again. Inserting 10 makes node 6 RR-heavy, so left-rotate 6. The final root is 8, with 6(5,7) on the left and 9(-,10) on the right. See it solved.

Question 6

Create an AVL tree with 70, 60, 80, 50, 65 and 68 how many leaves are there in the resultant tree?

• A. 2

• B. 3

• C. 4

• D. 5

Answer: B. 3. The first five insertions need no rotation. The path for 68 is 70 -> 60 -> 65 -> 68, making 70 an LR case. Left-rotate 60, then right-rotate 70. The final root is 65. Its left side is 60(50,-), and its right side is 70(68,80). The leaves are exactly 50, 68 and 80.

Question 7

How many rotations are required during the construction of an AVL tree if the following elements are to be added in the given sequence?

35,50,40,25,30,60,78,20,28

• A. 2 left rotations, 2 right rotations

• B. 2 left rotations, 3 right rotations

• C. 3 left rotations, 2 right rotations

• D. 3 left rotations, 1 right rotation

Answer: C. 3 left rotations, 2 right rotations. 35, 50, 40 causes RL at 35, giving L=1, R=1. Inserting 30 causes LR at 35, giving L=2, R=2. Inserting 78 causes RR at 50, giving L=3, R=2. The insertions 25, 60, 20 and 28 need no repair. The final root is 40, with left subtree 30(25(20,28),35) and right subtree 60(50,78). See it solved.

AVL Tree MCQs 8-10: maximum height and the Fibonacci recurrence

Question 8

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

• A. 2

• B. 3

• C. 4

• D. 5

Answer: B. 3. For minimum nodes at height h, use N(0)=1, N(1)=2, and N(h)=1+N(h-1)+N(h-2). Thus N(2)=4, N(3)=7, and N(4)=12. Seven nodes can realise height 3, but height 4 needs at least 12. Maximum height questions use minimum nodes per height. See it solved.

Question 9

What is the maximum height of an AVL tree with 12 nodes, assuming the height of a tree with a single node is 0?

• A. 3

• B. 4

• C. 5

• D. 6

• E. None of the above

Answer: B. 4. From N(2)=4 and N(3)=7, calculate N(4)=1+7+4=12 and N(5)=1+12+7=20. Twelve nodes exactly meet the minimum for height 4 but are eight short of height 5. Therefore 4 is the largest feasible height. See it solved.

Question 10

What is the maximum possible height of an AVL tree containing n nodes?

• A. ⌈log₂(n + 1)⌉

• B. 1.44 × log₂ n

• C. ⌊log₂(n + 1)⌋

• D. 1.64 × log₂ n

Answer: B. 1.44 × log₂ n. The recurrence grows approximately like phi^h. Inverting it gives h = O(log_phi n). Since 1/log_2(phi) is approximately 1.44, B is the standard asymptotic envelope. Additive constants are suppressed, so the option is not an exact equality for every n.

AVL Tree MCQs 11-12: search and insertion complexity

Question 11

What is the worst-case time complexity of inserting n² elements into an AVL tree with n elements initially?

• A. Θ(n⁴)

• B. Θ(n²)

• C. Θ(n² log n)

• D. Θ(n³)

Answer: C. Θ(n² log n). If the current size is m, one insertion costs Θ(log m). The tree grows from n to n + n², and throughout that range log m = Θ(log n). Multiplying n² insertions by Θ(log n) per insertion gives Θ(n² log n). See it solved.

Question 12

Which of the following is TRUE?

• A. The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)

• B. The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)

• C. The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)

• D. The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)

Answer: A. The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n). AVL balance guarantees height Theta(log n), so worst-case search is Theta(log n). A general BST can become a chain, making its worst-case search O(n). C reverses the guarantees, while B and D assign costs that do not follow from tree height. See it solved.

The short version and the next practice step

Keep this error ledger beside your next trace:

• Compute BF = left height - right height.

• Repair only when |BF| > 1.

• Identify LL, RR, LR or RL from the heavy child.

• After every rotation, recount from the changed subtree towards the root.

For height bounds, switch tools and use N(h)=1+N(h-1)+N(h-2). Retry Questions 5, 7, 8 and 11 without looking at the options. Together they test a full insertion trace, separate rotation counts, minimum nodes for a height, and a summed complexity argument.

Questions 8 and 12 also appear in Binary Tree MCQs: 11 Solved BST, AVL, Heaps (GATE), where they support a broad comparison across BSTs, AVL trees and heaps. Here Question 8 derives the AVL minimum-node recurrence, while Question 12 isolates the AVL search guarantee. For the complete Data Structures sequence around this focused AVL set, continue with GATE Guidance by Sanchit Sir.