What is an AVL Tree?
Learn what an AVL tree is, how rotations keep it balanced, and how to answer this data structures interview question well.
Expected Interview Answer
An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one, and it restores this balance after every insertion or deletion using rotations, guaranteeing O(log n) search, insert, and delete in the worst case.
Each node tracks a balance factor, the height of its left subtree minus the height of its right subtree, which must stay within -1, 0, or 1. When an insertion or deletion pushes a node's balance factor outside that range, the tree performs one of four rotation patterns, left, right, left-right, or right-left, at the lowest unbalanced ancestor to restore the invariant in O(1) work per rotation. Because the invariant is checked and repaired on the path back up to the root after every modification, the tree height never exceeds roughly 1.44 log2(n), which is what bounds every operation to O(log n) even in the worst case, unlike a plain BST which can degrade to O(n) on sorted input. AVL trees are stricter than red-black trees, giving faster lookups at the cost of more frequent rebalancing on writes, making them a good fit for read-heavy workloads.
- Guaranteed O(log n) search, insert, delete worst case
- Stricter balance than red-black trees means faster reads
- Height bounded to about 1.44 log2(n)
- Rotations restore balance in O(1) per rotation
AI Mentor Explanation
An AVL tree is like a tournament bracket organizer who insists neither half of any sub-bracket can have more than one extra round than the other half. Whenever a new team is added and one side of a sub-bracket grows a round deeper than allowed, the organizer performs a quick restructuring move, sliding a team or a whole mini-bracket across to the shallower side. This restructuring happens immediately at the smallest unbalanced sub-bracket, not the whole tournament, so it's a fast local fix rather than a full re-draw. Because this check happens after every single team addition, the whole bracket never grows lopsided, keeping every team's path to the final roughly the same short length.
Step-by-Step Explanation
Step 1
Insert like a normal BST
Place the new node following standard binary search tree comparison rules.
Step 2
Update heights and balance factor
Walk back up to the root, recomputing height and balance factor (left height minus right height) at each ancestor.
Step 3
Detect an imbalance
If a node’s balance factor becomes -2 or +2, it violates the AVL invariant.
Step 4
Apply the correct rotation
Choose left, right, left-right, or right-left rotation based on the imbalance shape, restoring balance in O(1) at that node.
What Interviewer Expects
- Define the balance invariant precisely (heights differ by at most 1)
- Name and describe all four rotation cases
- State the guaranteed O(log n) worst case for search, insert, delete
- Compare AVL trees to red-black trees on the read-vs-write tradeoff
Common Mistakes
- Forgetting to update heights on the path back to the root after insertion
- Confusing balance factor sign convention (left height minus right height)
- Applying a single rotation when a double rotation (left-right or right-left) is needed
- Assuming a plain unbalanced BST is already O(log n) in the worst case
Best Answer (HR Friendly)
“An AVL tree is a binary search tree that automatically keeps itself balanced, so no branch ever gets much deeper than its sibling branch. Every time I insert or delete, it checks a simple balance rule and fixes any violation with a quick local rotation, which is what guarantees search stays fast even in the worst case.”
Code Example
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(node):
return node.height if node else 0
def balance_factor(node):
return height(node.left) - height(node.right)
def update_height(node):
node.height = 1 + max(height(node.left), height(node.right))
def rotate_right(y):
x = y.left
y.left = x.right
x.right = y
update_height(y)
update_height(x)
return x
def rotate_left(x):
y = x.right
x.right = y.left
y.left = x
update_height(x)
update_height(y)
return y
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
update_height(node)
balance = balance_factor(node)
if balance > 1 and key < node.left.key:
return rotate_right(node)
if balance < -1 and key > node.right.key:
return rotate_left(node)
if balance > 1 and key > node.left.key:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and key < node.right.key:
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeFollow-up Questions
- How does an AVL tree compare to a red-black tree in terms of balance strictness?
- How would you delete a node from an AVL tree and rebalance afterward?
- Why does a plain unbalanced BST degrade to O(n) on sorted input?
- How would you verify a given binary tree satisfies the AVL invariant?
MCQ Practice
1. What is the maximum allowed difference between left and right subtree heights in an AVL tree?
The AVL invariant allows a balance factor of -1, 0, or 1 at every node.
2. What operation restores the AVL invariant after an insertion causes imbalance?
One of four rotation types (left, right, left-right, right-left) restores balance in O(1) at the affected node.
3. What is the worst-case time complexity of search in an AVL tree with n nodes?
The balance invariant bounds tree height to about 1.44 log2(n), guaranteeing O(log n) search even in the worst case.
Flash Cards
What invariant defines an AVL tree? — Left and right subtree heights of every node differ by at most 1.
How many rotation cases exist for rebalancing? — Four: left, right, left-right, and right-left.
What is the worst-case search time in an AVL tree? — O(log n), because height is bounded to about 1.44 log2(n).
How does an AVL tree compare to a red-black tree? — AVL trees are more strictly balanced, giving faster lookups but more frequent rebalancing on writes.