In an AVL tree, which values may the balance factor (height of left subtree minus height of right subtree) of any node take?
Correct answer A. −1, 0 or +1
Explanation
An AVL tree requires the heights of the two subtrees of every node to differ by at most one, so the balance factor must be −1, 0 or +1. If an insertion or deletion makes it +2 or −2, rotations restore balance. This guarantee keeps the height O(log n), so search, insert and delete all stay logarithmic even in the worst case.
Answer checked How we write and check questions
Discussion