AVL questions in GATE usually ask which rotation repairs an insertion or how few nodes a tree of height h can contain. Both are mechanical once the balance-factor convention and height convention are fixed. The usual errors are calling an LR case LL, rotating the wrong ancestor, and starting the node recurrence one level off.
What makes a binary search tree AVL
An AVL tree is a binary search tree in which every node stays height-balanced. Using the convention
balance factor = height(left subtree) - height(right subtree)every node must have balance factor -1, 0, or +1. A value of +2 means the node is too heavy on the left. A value of -2 means it is too heavy on the right.
After a BST insertion, walk upward from the inserted node and find the lowest unbalanced ancestor. Repairing that first unbalanced ancestor restores the height of the affected subtree, so insertion needs no further repair higher on that path. Deletion is slightly different because a height decrease can propagate upward and may require more than one rebalance.
If you need a quick refresh on ordering, children and subtree height, start with binary trees and binary search trees. AVL logic adds balance maintenance to the same BST foundation.
The four AVL rotation cases
Name the case by tracing two directions from the unbalanced node toward the inserted key:
Case | Insertion path | Repair |
|---|---|---|
LL | left, then left | one right rotation |
RR | right, then right | one left rotation |
LR | left, then right | left-rotate the child, then right-rotate the node |
RL | right, then left | right-rotate the child, then left-rotate the node |
LL and RR are straight paths, so one rotation works. LR and RL bend, so the child must first be rotated to straighten the path. The second rotation then lifts the middle key into the subtree root.
Rotations never reorder keys, so the inorder sequence is a free correctness check. If three keys are 10 < 20 < 30, the repaired local subtree should have 20 in the middle, with 10 on the left and 30 on the right.
Worked RR insertion step by step
Insert 10, 20, 30 into an empty AVL tree.
After inserting 10, it is the root. Insert 20; it becomes the right child of 10. With an empty subtree assigned height -1 and a leaf assigned height 0, the balance factor at 10 is
height(left) - height(right) = -1 - 0 = -1That is allowed.
Now insert 30. It becomes the right child of 20, producing the chain 10 -> 20 -> 30. At node 10, the left subtree has height -1 and the right subtree has height 1, so
balance factor at 10 = -1 - 1 = -2The path from 10 to the new key goes right, then right. This is RR, so perform one left rotation about 10. Node 20 becomes the local root, 10 becomes its left child, and 30 becomes its right child. Both child subtrees have height 0, so the balance factor at 20 is 0.
Compare that with inserting 30, 10, 20. The path at the unbalanced node 30 is left, then right, so it is LR. Left-rotate 10, then right-rotate 30. The final keys are again arranged as root 20 with children 10 and 30, but reaching that shape takes two rotations.
Height bounds and the minimum-node recurrence
State the convention before using a formula. Here, a leaf has height 0. Let N(h) be the minimum number of nodes in an AVL tree of height h.
To make a height-h AVL tree as sparse as possible, one child must have height h-1 and the other height h-2. A larger gap would violate the AVL condition. Adding the root gives
N(h) = N(h-1) + N(h-2) + 1
N(0) = 1
N(1) = 2Build the table upward from those base cases:
N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4
N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7
N(4) = N(3) + N(2) + 1 = 7 + 4 + 1 = 12
N(5) = N(4) + N(3) + 1 = 12 + 7 + 1 = 20Therefore the minimum number of nodes at height 4 is 12. Read the table in reverse too: a 12-node AVL tree can reach height 4, but cannot reach height 5, because height 5 requires at least 20 nodes.
The recurrence grows like the Fibonacci sequence, which keeps AVL height logarithmic. For the opposite bound, the maximum number of nodes in any binary tree of height h is the full-tree count 2^(h+1) - 1. At height 4, that is 2^5 - 1 = 31. An AVL tree of height 4 can therefore contain from 12 through 31 nodes.
The same table answers the reverse question, the one asked whenever a node count is given: how tall can that tree be? Continue the recurrence past height 5.
N(6) = N(5) + N(4) + 1 = 20 + 12 + 1 = 33
N(7) = N(6) + N(5) + 1 = 33 + 20 + 1 = 54
N(8) = N(7) + N(6) + 1 = 54 + 33 + 1 = 88
N(9) = N(8) + N(7) + 1 = 88 + 54 + 1 = 143For 100 nodes, take the largest h whose minimum still fits. N(8) = 88 fits inside 100 and N(9) = 143 does not, so a 100-node AVL tree reaches height 8 at most. The closed-form bound h < 1.44 log2(n+2) - 0.328 gives 9 for the same input, because it is an upper bound and not tight. The recurrence table is the one to trust in the exam hall.
Traps GATE plants in AVL questions
Keep these checks beside the rough work:
Confirm whether balance factor means left minus right or right minus left. The rotation does not change, but the sign does.
Read both directions in the collision path. Left then right is LR, not LL.
Rotate the lowest unbalanced ancestor after insertion, not the root automatically.
Keep the height bases beside the recurrence. With
N(0)=1andN(1)=2, raw Fibonacci numbers are off by one.Separate minimum nodes from maximum nodes. The AVL recurrence gives the minimum;
2^(h+1)-1gives the maximum.
Tree reconstruction questions use much of the same structural reasoning. The walkthrough on constructing a binary tree from traversals is useful practice for keeping subtree boundaries precise.
How GATE tests AVL trees
Expect an insertion sequence, a request for the resulting root, a rotation count, a minimum-node calculation, or a maximum possible height for a given node count. The KnowledgeGate question bank carries about 1,500 Data Structure questions covering these patterns and related tree topics.
For current subject weightage or paper-pattern details, check the official GATE portal run by that year's organising IIT. The four cases and the recurrence themselves do not change. The GATE category connects this topic to the rest of the preparation path.
Short version and next step
Trace two directions to identify LL, RR, LR or RL. Repair the lowest unbalanced ancestor after insertion. For height bounds, use N(h)=N(h-1)+N(h-2)+1 with the exact base cases supplied by the question.
Make the process automatic with rotation walkthroughs in GATE Guidance by Sanchit Sir, then use timed Data Structure sets in the GATE Test Series to check whether you can choose and execute a rotation without trial and error.
