Skip to interview prep
Apexed

22. How does an AVL tree stay balanced?

HardTrees

Technical
Show model answer

An AVL tree keeps, for every node, the heights of its two subtrees within 1 of each other. After an insert or delete, it walks back up and fixes any node whose balance factor becomes ±2 with a rotation: single rotations for the left-left and right-right cases, and double rotations for left-right and right-left.

This guarantees height O(log n), so search, insert and delete are O(log n). Red-black trees allow slightly more imbalance in exchange for fewer rotations on updates.

How does an AVL tree stay balanced — Data structures & algorithms interview question — Apexed