Advanced · Module 20 · Lesson 2 of 5

AVL rotations

An AVL tree keeps the heights of every node's two subtrees within one of each other. After an insert, at most one or two rotations, local pointer rearrangements that preserve key order, restore that rule and keep the height below 1.44 log₂ n.

ProAbout 15 minutes

By the end you can

State the AVL balance invariant and compute balance factors
Perform single and double rotations, and choose between them from the shape of the imbalance
Explain why the invariant bounds the height at about 1.44 log₂ n

Builds on Why binary search trees degrade.

01 · A question first

Sorted input turned a plain binary search tree into a chain. An AVL tree receiving the same input stays as shallow as possible, and it does so by changing three pointers at a time. How can a change that small fix the shape of a whole tree, without ever putting a key out of order?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

A local rule with a global effect
Rotations
The four cases
The trace, step by step
Why the height stays logarithmic
Costs and trade-offs
Augmenting the tree
Pseudocode & Multi-Language Implementations (C++, Java, Python)

See plans Already a member? Sign in

03 · Practice

Practice · easy · LeetCodeBalanced binary treeDecide whether every node's subtrees differ in height by at most one, in a single O(n) pass.Practice · medium · LeetCodeBalance a binary search treeTurn any binary search tree into a balanced one with the same keys, by flattening it in order and rebuilding.

Asked in interviews

Insert 30, 20, 25 into an AVL tree. Which rotations happen, and why?

Something wrong with this lesson? Report a problem