The AVL tree balance factor shows whether a node’s left and right subtrees remain close in height. After each insertion, calculate this value while moving from the new node toward the root. A value outside the range -1 to 1 identifies the ancestor that needs a rotation.

These AVL tree examples use one height convention and one sign convention throughout, so each LL, RR, LR, or RL case follows directly from the observed values.

What Is the AVL Tree Balance Factor? Set Height and Sign Convention First

Set the height of an empty child to 0 and the height of a leaf to 1. For every node:

height(node) = 1 + max(height(left), height(right))

Using left height minus right height, the balance factor formula is:

balance factor = height(left subtree) − height(right subtree)

• +1: the left subtree is one level taller.
• 0: both subtrees have equal height.
• -1: the right subtree is one level taller.

An AVL node is height-balanced when its factor is -1, 0, or +1. A factor of +2 means left-heavy imbalance; -2 means right-heavy imbalance. The sign convention matters: reversing the subtraction would reverse the case labels.

How Do You Calculate the Balance Factor in an AVL Tree and Find the First Unbalanced Ancestor?

After inserting a key as in an ordinary binary search tree, start at that new leaf and move upward. At each node, update its height first, then calculate its balance factor. The first unbalanced ancestor is the first node encountered with a factor of +2 or -2. Because the search proceeds upward, this is the lowest unbalanced ancestor and normally the point where you apply the rotation.

1. Insert the key according to binary-search-tree ordering.
2. Recompute each ancestor’s height using the larger child height.
3. Calculate left height minus right height.
4. Use the heavy child and the inserted key’s direction to identify LL, RR, LR, or RL.
5. Rotate, then recompute heights from the lowest changed node upward.

Which AVL Tree Examples Show LL and RR Rotations With Updated Heights?

LL case: Insert 30, then 20, then 10. The path leans left twice:

30(+2)
↙ 20(+1)
↙ 10(0)

Node 30 is the first unbalanced ancestor. Apply one right rotation at 30. Node 20 becomes the root, with 10 as its left child and 30 as its right child. Each leaf has height 1; node 20 has height 2 and balance factor 0. The rotation changes structure first, so calculate the lower node’s height before the new root’s height.

RR case: Insert 10, then 20, then 30. The path leans right twice. Node 10 has factor -2, so apply one left rotation at 10. Node 20 becomes the root, with 10 on the left and 30 on the right. Both leaves have height 1, and node 20 has height 2 with factor 0.

How Does AVL Tree Balancing Resolve LR and RL Cases With Updated Heights?

LR case: Insert 30, then 10, then 20. Node 30 has factor +2, but its left child, 10, has factor -1. This is a left-right bend, so use two rotations:

1. Rotate left at 10. The subtree becomes 20 with 10 as its left child.
2. Rotate right at 30. Node 20 becomes the subtree root, with 10 and 30 as children.

After the structural changes, 10 and 30 each have height 1. Node 20 receives height 2 and factor 0.

RL case: Insert 10, then 30, then 20. Node 10 has factor -2, while its right child, 30, has factor +1. Apply the mirror sequence:

1. Rotate right at 30, making 20 the root of that subtree with 30 on the right.
2. Rotate left at 10, making 20 the subtree root with 10 on the left.

Again, the two leaves have height 1, and the new subtree root 20 has height 2 and factor 0. This is the practical rule for AVL tree balancing: single-direction growth uses one rotation; a bend uses the child rotation first, followed by the opposite rotation at the unbalanced ancestor.