Where The First Rotation Fires
This AVL tree satisfies the height invariant, meaning at every node the two subtree heights differ by at most 1:
20
/ \
8 30
/ \ / \
3 12 25 40
Insert 27, then insert 28. The first insert leaves the invariant intact. The second one breaks it at more than one node.
At which node is the lowest violation, and what fixes it?
Sign in to answer questions and track your progress
Sign In