What is an AVL tree, and what makes it balanced?
An AVL tree is a self-balancing binary search tree (BST) in which the height balance of subtrees is controlled for every node. It is named after its inventors, Adelson-Velsky and Landis (AVL).
Main balancing property
For every node, the difference between the heights of its left and right subtree is no more than 1: [ |height(left) - height(right)| \leq 1 ]
If this balance is broken after an insertion or deletion, the tree automatically performs a rotation to restore the balance.
Why this matters
Thanks to this condition, the height of an AVL tree always stays around O(log n), so all operations, search, insertion, deletion, run fast.
Example
Before insertion:
30
/
20
/
10
After balancing:
20
/ \
10 30The tree performs a right rotation to restore balance.
Main types of rotations
- Right Rotation - when the imbalance is in the left subtree.
- Left Rotation - when the imbalance is in the right subtree.
- Left-right and right-left - for more complex cases.
Summary
An AVL tree is a binary search tree in which a nearly ideal height balance is maintained after every operation. This guarantees that search, insertion, and deletion run in O(log n), while the tree's structure stays "dense" and efficient.
Short Answer
Interview readyA concise answer to help you respond confidently on this topic during an interview.