Problem Statement
In an AVL tree, what is the maximum height difference allowed between left and right subtrees of any node?
Explanation
In an AVL tree, the balance factor of any node, which is the difference between the heights of left and right subtrees, must be at most 1. This strict balance criterion ensures that the tree remains approximately balanced and all operations maintain O of log n time complexity.
When an insertion or deletion causes the balance factor to exceed 1 or become less than negative 1, the tree performs rotations to restore balance. The four types of rotations are left rotation, right rotation, left-right rotation, and right-left rotation. This automatic rebalancing is what makes AVL trees self-balancing binary search trees and guarantees logarithmic height.
Code Solution
SolutionRead Only
// AVL Tree Node
class AVLNode {
int data;
AVLNode left, right;
int height;
// Balance factor = height(left) - height(right)
// Must be in range [-1, 0, 1]
}
// Example balanced AVL tree:
// 10 (BF=0)
// / \
// 5 15 (BF=-1, 0)
// / \
// 3 7 (BF=0, 0)
// After inserting 2, becomes unbalanced:
// 10 (BF=2) - UNBALANCED!
// / \
// 5 15
// / \
// 3 7
// /
// 2
// Right rotation restores balance:
// 5 (BF=0)
// / \
// 3 10
// / / \
// 2 7 15
int getBalance(AVLNode node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}Practice Sets
This question appears in the following practice sets:
