Data Structures & AlgorithmsHeight-Balanced Trees — Concept & Invariants

Height-Balanced Trees — Concept & Invariants

LevelIntermediate

Duration75 mins

TopicHeight-Balanced Trees — Concept & Invariants

2 / 4

Balance Factor Concept

Tracking Balance Efficiently

In the previous page, we established that a tree is height-balanced when |height(left) - height(right)| ≤ 1 holds for every node. This definition is mathematically precise, but it presents a practical challenge: how do we efficiently check and maintain this condition?

The naive approach—recomputing heights from scratch after every insertion or deletion—would require O(n) time per operation, defeating the purpose of using a balanced tree. We need a way to track balance information incrementally, updating only what changes.

Enter the balance factor: a simple integer stored at each node that captures the essence of that node's balance state in a single number. This elegant optimization is the key to O(log n) rebalancing.

What You Will Learn

By the end of this page, you will understand what a balance factor is, how to compute it, what different balance factor values mean, how balance factors propagate up the tree during operations, and how they enable efficient violation detection.

Definition of Balance Factor

The balance factor is deceptively simple in its definition, yet profoundly powerful in its implications.

Definition: Balance Factor

The balance factor of a node is the height of its left subtree minus the height of its right subtree:

BF(node) = height(node.left) - height(node.right)

Using our convention that null nodes have height -1:

If a node has only a left child of height 2: BF = 2 - (-1) = 3
If a node has only a right child of height 1: BF = (-1) - 1 = -2
If a node has equal-height subtrees of height 1 each: BF = 1 - 1 = 0
If a node has a left subtree of height 2 and right subtree of height 1: BF = 2 - 1 = 1

Sign Convention

The balance factor can be positive, negative, or zero. A positive BF means the left subtree is taller (left-heavy). A negative BF means the right subtree is taller (right-heavy). A zero BF means both subtrees have equal height (perfectly balanced at this node).

Connection to height balance:

Recall that a tree is height-balanced when |height(left) - height(right)| ≤ 1 at every node. Since BF = height(left) - height(right), this condition becomes:

|BF| ≤ 1

Or equivalently: BF ∈ {-1, 0, +1}

This is the AVL balance condition expressed in terms of balance factors: every node in a valid AVL tree has a balance factor of -1, 0, or +1.

Any other value indicates imbalance:

BF = +2 or higher: left subtree is too tall (left-heavy violation)
BF = -2 or lower: right subtree is too tall (right-heavy violation)

Interpreting Balance Factor Values

Each balance factor value tells a specific story about the structure of the subtree rooted at that node. Let's examine what each value means:

Balance Factor Interpretation
BF Value	Meaning	Structural Implication	Status
+2 or higher	Severely left-heavy	Left subtree at least 2 levels taller than right	❌ VIOLATION - needs rebalancing
+1	Slightly left-heavy	Left subtree exactly 1 level taller than right	✓ Valid AVL state
0	Perfectly balanced	Both subtrees have identical height	✓ Valid AVL state
-1	Slightly right-heavy	Right subtree exactly 1 level taller than left	✓ Valid AVL state
-2 or lower	Severely right-heavy	Right subtree at least 2 levels taller than left	❌ VIOLATION - needs rebalancing

balance-factor-examples.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
EXAMPLE 1: BF = 0 (Perfectly Balanced at Node A)
 
        A [BF=0]
       / \
      B   C
     /     \
    D       E
 
height(left subtree of A) = 1
height(right subtree of A) = 1
BF(A) = 1 - 1 = 0
 
 
EXAMPLE 2: BF = +1 (Slightly Left-Heavy at Node A)
 
        A [BF=+1]
       / \
      B   C
     / \
    D   E
 
height(left subtree of A) = 2
height(right subtree of A) = 1
BF(A) = 2 - 1 = +1
 
 
EXAMPLE 3: BF = +2 (VIOLATION at Node A)
 
        A [BF=+2] ← VIOLATION!
       / 
      B [BF=0]    
     / \
    D   E
 
height(left subtree of A) = 2
height(right subtree of A) = -1 (null)
BF(A) = 2 - (-1) = 3  (actually +3, not +2!)
 
 
EXAMPLE 4: BF = -1 (Slightly Right-Heavy at Node A)
 
        A [BF=-1]
       / \
      B   C
           \
            E
 
height(left subtree of A) = 0
height(right subtree of A) = 1
BF(A) = 0 - 1 = -1

The intuition behind the sign:

Think of the balance factor as indicating which direction the node "leans":

Positive BF → The node leans LEFT (left subtree is taller)
Zero BF → The node is upright (balanced)
Negative BF → The node leans RIGHT (right subtree is taller)

When a node leans too far in either direction (|BF| ≥ 2), it risks "falling over"—this is when rotations are needed to rebalance the tree.

Storing Balance Factors in Nodes

To use balance factors efficiently, we augment the standard BST node structure with an additional field. This is a classic example of augmented data structures—storing extra information to accelerate specific queries or operations.

avl-node-structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Standard BST Node
interface BSTNode<T> {
    value: T;
    left: BSTNode<T> | null;
    right: BSTNode<T> | null;
}
 
// AVL Node with Balance Factor
interface AVLNode<T> {
    value: T;
    left: AVLNode<T> | null;
    right: AVLNode<T> | null;
    balanceFactor: number;  // -1, 0, or +1 for valid nodes
}
 
// Alternative: Store Height Instead
interface AVLNodeWithHeight<T> {
    value: T;
    left: AVLNodeWithHeight<T> | null;
    right: AVLNodeWithHeight<T> | null;
    height: number;  // Derive BF when needed: BF = h(left) - h(right)
}

Balance Factor vs. Height Storage:

There are two common approaches to tracking balance:

Approach 1: Store Balance Factor Directly

Storage: 1 integer per node (values -1, 0, +1, possibly ±2 during rebalancing)
Pro: Minimal storage (can even use 2 bits)
Con: Computing absolute heights requires traversal

Approach 2: Store Height, Derive Balance Factor

Storage: 1 integer per node (height value, typically 0 to ~30 for reasonable trees)
Pro: Easy to compute BF when needed: bf = height(left) - height(right)
Pro: Absolute heights available without traversal
Con: Slightly more storage (though typically negligible)

Most implementations use the height-based approach because it simplifies the code and the storage overhead is minimal. The balance factor is computed on-the-fly when needed.

height-and-balance.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Practical AVL Node Implementation
class AVLNode<T> {
    value: T;
    left: AVLNode<T> | null = null;
    right: AVLNode<T> | null = null;
    height: number = 0;  // Height of this node (leaf = 0)
    
    constructor(value: T) {
        this.value = value;
    }
}
 
// Utility functions
function getHeight<T>(node: AVLNode<T> | null): number {
    return node === null ? -1 : node.height;
}
 
function getBalanceFactor<T>(node: AVLNode<T> | null): number {
    if (node === null) return 0;
    return getHeight(node.left) - getHeight(node.right);
}
 
function updateHeight<T>(node: AVLNode<T>): void {
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
 
// Example usage
function isBalanced<T>(node: AVLNode<T> | null): boolean {
    if (node === null) return true;
    
    const bf = getBalanceFactor(node);
    return Math.abs(bf) <= 1 && isBalanced(node.left) && isBalanced(node.right);
}

The Height Field is Your Friend

Storing height rather than balance factor directly makes debugging much easier—you can print node heights and immediately understand the tree structure. It also makes certain operations (like computing tree height) O(1) instead of O(n).

Balance Factor Propagation During Operations

The real power of balance factors emerges during insertions and deletions. When we modify the tree, balance factors of affected nodes must be updated. The key insight is that changes propagate upward along the path from the modification point to the root.

Insertion Propagation:

When we insert a new node:

The insertion happens at a leaf position
The new node has BF = 0 (it has no children)
Heights (and thus balance factors) may change for ancestors along the insertion path
We walk back toward the root, updating heights and checking balance factors
If any node's BF becomes ±2, we've found a violation that needs fixing

insertion-propagation.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
EXAMPLE: Inserting value 25 into an AVL tree
 
BEFORE INSERTION:
                30 [h=2, BF=-1]
               /  \
        20[h=1,BF=0] 40[h=0,BF=0]
         /  \
   10[h=0]  (null)
 
STEP 1: Insert 25 as right child of 20
                30 [h=?, BF=?]   ← needs update
               /  \
        20[h=?, BF=?]  40[h=0,BF=0]  ← needs update
         /  \
   10[h=0]  25[h=0, BF=0]  ← new node
 
STEP 2: Update height of node 20
  Old: height(10) = 0, height(null) = -1 → h(20) = 1
  New: height(10) = 0, height(25) = 0 → h(20) = 1
  Height unchanged! BF(20) = 0 - 0 = 0
 
STEP 3: Update height of node 30
  height(20) = 1, height(40) = 0 → h(30) = 2
  Height unchanged! BF(30) = 1 - 0 = +1 (was -1, now +1)
  Wait, that's not right. Let me recalculate...
  
  Actually:
  Old state: h(30) = 1 + max(h(20), h(40)) = 1 + max(1, 0) = 2
  New state: Same! h(20) didn't change.
 
AFTER INSERTION:
                30 [h=2, BF=+1]  ← BF changed from -1 to +1
               /  \
        20[h=1,BF=0]  40[h=0,BF=0]
         /  \
   10[h=0]  25[h=0]
 
Result: Tree remains balanced (all BFs in {-1, 0, +1})

Critical observation: Early termination

When propagating balance factor updates upward, we can often stop before reaching the root:

If a node's height doesn't change, no ancestors will change either. We can stop.
If a node's BF was +1 and becomes 0 (or -1 becomes 0), the subtree's height decreased, but the node absorbed the change. Ancestors won't see a height change.
If a node's BF was 0 and becomes ±1, the subtree's height increased. Continue propagating.
If a node's BF becomes ±2, we've found a violation. Handle it (via rotation), then potentially continue.

This early termination is crucial for efficiency—many insertions only affect a few nodes near the insertion point.

Deletion Is More Complex

Insertion can cause at most one balance violation (the first ±2 we encounter), which is fixed by one or two rotations. Deletion, however, can require rebalancing at multiple nodes along the path because fixing one imbalance might create another higher up. We'll cover this in detail when we discuss AVL operations.

Using Balance Factors for Violation Detection

The balance factor isn't just a passive indicator—it's an active diagnostic tool. When a balance factor reaches ±2, it tells us not only that rebalancing is needed, but also what type of rotation to perform.

The Four Imbalance Cases:

When BF(node) = +2 (left-heavy violation), we look at the left child's balance factor:

If BF(left child) ≥ 0: Left-Left (LL) case → Single right rotation
If BF(left child) < 0: Left-Right (LR) case → Double rotation (left then right)

When BF(node) = -2 (right-heavy violation), we look at the right child's balance factor:

If BF(right child) ≤ 0: Right-Right (RR) case → Single left rotation
If BF(right child) > 0: Right-Left (RL) case → Double rotation (right then left)

Imbalance Detection Using Balance Factors
Parent BF	Child BF	Case Name	Imbalance Shape	Fix
+2	≥ 0	Left-Left (LL)	Straight line left	Single right rotation
+2	< 0	Left-Right (LR)	Zig-zag left-right	Left rotation on child, then right rotation on parent
-2	≤ 0	Right-Right (RR)	Straight line right	Single left rotation
-2	0	Right-Left (RL)	Zig-zag right-left	Right rotation on child, then left rotation on parent

violation-detection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type RotationType = 'LL' | 'LR' | 'RR' | 'RL' | 'BALANCED';
 
function detectViolationType<T>(node: AVLNode<T>): RotationType {
    const bf = getBalanceFactor(node);
    
    // No violation
    if (Math.abs(bf) <= 1) {
        return 'BALANCED';
    }
    
    // Left-heavy violation (BF = +2)
    if (bf > 1) {
        const leftBF = getBalanceFactor(node.left);
        // If left child is left-heavy or balanced: LL case
        // If left child is right-heavy: LR case
        return leftBF >= 0 ? 'LL' : 'LR';
    }
    
    // Right-heavy violation (BF = -2)
    if (bf < -1) {
        const rightBF = getBalanceFactor(node.right);
        // If right child is right-heavy or balanced: RR case
        // If right child is left-heavy: RL case
        return rightBF <= 0 ? 'RR' : 'RL';
    }
    
    return 'BALANCED';  // Should never reach here
}
 
// Complete rebalance function
function rebalance<T>(node: AVLNode<T>): AVLNode<T> {
    updateHeight(node);
    const violationType = detectViolationType(node);
    
    switch (violationType) {
        case 'LL':
            return rotateRight(node);
        case 'LR':
            node.left = rotateLeft(node.left!);
            return rotateRight(node);
        case 'RR':
            return rotateLeft(node);
        case 'RL':
            node.right = rotateRight(node.right!);
            return rotateLeft(node);
        default:
            return node;  // Already balanced
    }
}

The elegance of this approach:

Balance factors give us O(1) violation detection and classification. We don't need to examine the entire subtree or perform complex analysis—just two simple integer comparisons tell us exactly what's wrong and how to fix it.

This is the power of maintaining invariants with local information: global properties (tree height bound) emerge from local constraints (balance factors at each node), and violations can be detected and fixed with local operations (rotations involving at most 3 nodes).

Building a Mental Model for Balance Factors

To work effectively with AVL trees, you need to internalize how balance factors behave. Here are key mental models and patterns:

Mental Models for Balance Factors

•The Scale Analogy — Think of each node as a balance scale. The left subtree and right subtree are weights on either side. BF tells you which side is heavier and by how much. ±1 is a slight tilt (acceptable), ±2 is about to tip over (needs fixing).
•The Absorption Principle — When a subtree grows by 1, the parent node's BF changes by ±1. If the parent was already leaning the opposite way (e.g., was -1 and left subtree grew), the growth is 'absorbed' and the parent becomes balanced (BF = 0).
•The Propagation Limit — Height changes propagate up only when a node goes from BF=0 to BF=±1. If a node absorbs the change (±1 → 0), height doesn't change, and propagation stops.
•The Single Violation Rule (for Insertion) — An insertion can create at most one ±2 violation. Once fixed by rotation, the subtree's height is restored to its pre-insertion value, so ancestors are unaffected.
•The Direction Tells the Story — BF = +2 at node X means 'too many nodes on the left.' Look at X's left child Y to determine shape: if Y also leans left or is balanced (BF ≥ 0), it's a straight line (LL). If Y leans right (BF < 0), it's a zig-zag (LR).

Practice exercise: Trace insertions mentally

Given a sequence of insertions, practice predicting:

Where each node will be inserted (standard BST logic)
Which nodes will have their heights updated
Which nodes (if any) will have BF violations
What rotation type will be needed

This mental tracing builds the intuition that makes AVL trees feel natural rather than mysterious.

Debugging with Balance Factors

When debugging AVL implementations, print the tree with balance factors at each node. Invalid trees will have ±2 (or worse) somewhere. If rotations aren't updating balance factors correctly, you'll see impossible configurations like BF = +3 or descendants with higher heights than ancestors.

Common Misconceptions About Balance Factors

Balance factors are conceptually simple, but several misconceptions are common among those learning AVL trees. Let's address them directly:

Misconceptions to Avoid

•Misconception: BF tells you the node count difference — Wrong. BF = height(left) - height(right), not nodes(left) - nodes(right). A subtree with 100 nodes on the left and 50 nodes on the right might still have BF = 0 if both subtrees have the same height.
•Misconception: BF = 0 means equal subtree sizes — Wrong. A left subtree with nodes arranged as a perfect binary tree of height 3 (15 nodes) and a right subtree that's a straight line of height 3 (4 nodes) would both contribute height 3. BF = 0, but 15 ≠ 4.
•Misconception: A rotation always creates BF = 0 at the rotated node — Not always. After a single rotation, the new root might have BF = 0 or BF = ±1 depending on the original configuration. The key is that all BFs become valid (within ±1), not that they all become 0.
•Misconception: BF changes only for nodes on the insertion path — Mostly true, but subtly wrong. After a rotation, nodes involved in the rotation might change their parent-child relationships, affecting their heights and BFs. However, the affected region is still local.
•Misconception: BF = +2 always means 'rotate right' — Almost true for LL case, but wrong for LR case. When BF = +2 and the left child has BF < 0, you need a double rotation (left on child, then right on parent). The child's BF determines whether it's a straight-line or zig-zag imbalance.

The subtle point about node count vs. height:

Consider two subtrees:

Left: A complete binary tree with 7 nodes (height 2)
Right: A single chain of 3 nodes (height 2)

Both have height 2, so BF = 0. But the left has more than twice as many nodes!

This illustrates why height balance doesn't guarantee anything about node distribution—only about height. This is fine for complexity analysis (operations are O(h), not O(nodes)), but sometimes confuses learners who expect "balanced" to mean "equal-sized."

Summary: The Balance Factor as Your Guide

The balance factor is a simple but powerful concept that underlies all AVL tree operations. Let's consolidate what we've learned:

Key Takeaways

•BF = height(left) - height(right) — The balance factor is the height difference between subtrees, with positive meaning left-heavy and negative meaning right-heavy.
•Valid BF values are -1, 0, +1 — Any other value indicates a violation of the AVL property that must be fixed by rotation.
•Store height, compute BF on demand — Most implementations store height at each node and derive BF when needed, simplifying code and debugging.
•Changes propagate upward — When we modify the tree, height and BF updates propagate from the modification point toward the root along the path.
•BF at violation point + BF of child determines rotation type — The combination of the violating node's BF (±2) and its heavy child's BF tells us exactly which of the four rotation cases applies.
•Early termination is possible — When a node absorbs a height change (BF goes toward 0), propagation stops because ancestors won't see any height change.

What's next:

Now that we understand how to track balance with balance factors, we need to understand the broader concept of invariants—properties that we maintain at all times to guarantee the tree's correct behavior. The next page explores what invariants balanced trees maintain and how these invariants work together to provide performance guarantees.

Page Complete

You now understand the balance factor—the key to efficient balance tracking in AVL trees. This simple integer (BF = height(left) - height(right)) stored at each node enables O(1) violation detection and O(log n) correction, transforming height balance from a theoretical constraint into a practical reality.

2 / 4

Loading learning content...

Data Structures & AlgorithmsHeight-Balanced Trees — Concept & Invariants

Height-Balanced Trees — Concept & Invariants

LevelIntermediate

Duration75 mins

TopicHeight-Balanced Trees — Concept & Invariants

2 / 4

Balance Factor Concept

Tracking Balance Efficiently

What You Will Learn

Definition of Balance Factor

The balance factor is deceptively simple in its definition, yet profoundly powerful in its implications.

Definition: Balance Factor

The balance factor of a node is the height of its left subtree minus the height of its right subtree:

BF(node) = height(node.left) - height(node.right)

Using our convention that null nodes have height -1:

If a node has only a left child of height 2: BF = 2 - (-1) = 3
If a node has only a right child of height 1: BF = (-1) - 1 = -2
If a node has equal-height subtrees of height 1 each: BF = 1 - 1 = 0
If a node has a left subtree of height 2 and right subtree of height 1: BF = 2 - 1 = 1

Sign Convention

Connection to height balance:

Recall that a tree is height-balanced when |height(left) - height(right)| ≤ 1 at every node. Since BF = height(left) - height(right), this condition becomes:

|BF| ≤ 1

Or equivalently: BF ∈ {-1, 0, +1}

This is the AVL balance condition expressed in terms of balance factors: every node in a valid AVL tree has a balance factor of -1, 0, or +1.

Any other value indicates imbalance:

BF = +2 or higher: left subtree is too tall (left-heavy violation)
BF = -2 or lower: right subtree is too tall (right-heavy violation)

Interpreting Balance Factor Values

Each balance factor value tells a specific story about the structure of the subtree rooted at that node. Let's examine what each value means:

Balance Factor Interpretation
BF Value	Meaning	Structural Implication	Status
+2 or higher	Severely left-heavy	Left subtree at least 2 levels taller than right	❌ VIOLATION - needs rebalancing
+1	Slightly left-heavy	Left subtree exactly 1 level taller than right	✓ Valid AVL state
0	Perfectly balanced	Both subtrees have identical height	✓ Valid AVL state
-1	Slightly right-heavy	Right subtree exactly 1 level taller than left	✓ Valid AVL state
-2 or lower	Severely right-heavy	Right subtree at least 2 levels taller than left	❌ VIOLATION - needs rebalancing

balance-factor-examples.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
EXAMPLE 1: BF = 0 (Perfectly Balanced at Node A)
 
        A [BF=0]
       / \
      B   C
     /     \
    D       E
 
height(left subtree of A) = 1
height(right subtree of A) = 1
BF(A) = 1 - 1 = 0
 
 
EXAMPLE 2: BF = +1 (Slightly Left-Heavy at Node A)
 
        A [BF=+1]
       / \
      B   C
     / \
    D   E
 
height(left subtree of A) = 2
height(right subtree of A) = 1
BF(A) = 2 - 1 = +1
 
 
EXAMPLE 3: BF = +2 (VIOLATION at Node A)
 
        A [BF=+2] ← VIOLATION!
       / 
      B [BF=0]    
     / \
    D   E
 
height(left subtree of A) = 2
height(right subtree of A) = -1 (null)
BF(A) = 2 - (-1) = 3  (actually +3, not +2!)
 
 
EXAMPLE 4: BF = -1 (Slightly Right-Heavy at Node A)
 
        A [BF=-1]
       / \
      B   C
           \
            E
 
height(left subtree of A) = 0
height(right subtree of A) = 1
BF(A) = 0 - 1 = -1

The intuition behind the sign:

Think of the balance factor as indicating which direction the node "leans":

Positive BF → The node leans LEFT (left subtree is taller)
Zero BF → The node is upright (balanced)
Negative BF → The node leans RIGHT (right subtree is taller)

When a node leans too far in either direction (|BF| ≥ 2), it risks "falling over"—this is when rotations are needed to rebalance the tree.

Storing Balance Factors in Nodes

avl-node-structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Standard BST Node
interface BSTNode<T> {
    value: T;
    left: BSTNode<T> | null;
    right: BSTNode<T> | null;
}
 
// AVL Node with Balance Factor
interface AVLNode<T> {
    value: T;
    left: AVLNode<T> | null;
    right: AVLNode<T> | null;
    balanceFactor: number;  // -1, 0, or +1 for valid nodes
}
 
// Alternative: Store Height Instead
interface AVLNodeWithHeight<T> {
    value: T;
    left: AVLNodeWithHeight<T> | null;
    right: AVLNodeWithHeight<T> | null;
    height: number;  // Derive BF when needed: BF = h(left) - h(right)
}

Balance Factor vs. Height Storage:

There are two common approaches to tracking balance:

Approach 1: Store Balance Factor Directly

Storage: 1 integer per node (values -1, 0, +1, possibly ±2 during rebalancing)
Pro: Minimal storage (can even use 2 bits)
Con: Computing absolute heights requires traversal

Approach 2: Store Height, Derive Balance Factor

Storage: 1 integer per node (height value, typically 0 to ~30 for reasonable trees)
Pro: Easy to compute BF when needed: bf = height(left) - height(right)
Pro: Absolute heights available without traversal
Con: Slightly more storage (though typically negligible)

Most implementations use the height-based approach because it simplifies the code and the storage overhead is minimal. The balance factor is computed on-the-fly when needed.

height-and-balance.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Practical AVL Node Implementation
class AVLNode<T> {
    value: T;
    left: AVLNode<T> | null = null;
    right: AVLNode<T> | null = null;
    height: number = 0;  // Height of this node (leaf = 0)
    
    constructor(value: T) {
        this.value = value;
    }
}
 
// Utility functions
function getHeight<T>(node: AVLNode<T> | null): number {
    return node === null ? -1 : node.height;
}
 
function getBalanceFactor<T>(node: AVLNode<T> | null): number {
    if (node === null) return 0;
    return getHeight(node.left) - getHeight(node.right);
}
 
function updateHeight<T>(node: AVLNode<T>): void {
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
 
// Example usage
function isBalanced<T>(node: AVLNode<T> | null): boolean {
    if (node === null) return true;
    
    const bf = getBalanceFactor(node);
    return Math.abs(bf) <= 1 && isBalanced(node.left) && isBalanced(node.right);
}

The Height Field is Your Friend

Balance Factor Propagation During Operations

Insertion Propagation:

When we insert a new node:

The insertion happens at a leaf position
The new node has BF = 0 (it has no children)
Heights (and thus balance factors) may change for ancestors along the insertion path
We walk back toward the root, updating heights and checking balance factors
If any node's BF becomes ±2, we've found a violation that needs fixing

insertion-propagation.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
EXAMPLE: Inserting value 25 into an AVL tree
 
BEFORE INSERTION:
                30 [h=2, BF=-1]
               /  \
        20[h=1,BF=0] 40[h=0,BF=0]
         /  \
   10[h=0]  (null)
 
STEP 1: Insert 25 as right child of 20
                30 [h=?, BF=?]   ← needs update
               /  \
        20[h=?, BF=?]  40[h=0,BF=0]  ← needs update
         /  \
   10[h=0]  25[h=0, BF=0]  ← new node
 
STEP 2: Update height of node 20
  Old: height(10) = 0, height(null) = -1 → h(20) = 1
  New: height(10) = 0, height(25) = 0 → h(20) = 1
  Height unchanged! BF(20) = 0 - 0 = 0
 
STEP 3: Update height of node 30
  height(20) = 1, height(40) = 0 → h(30) = 2
  Height unchanged! BF(30) = 1 - 0 = +1 (was -1, now +1)
  Wait, that's not right. Let me recalculate...
  
  Actually:
  Old state: h(30) = 1 + max(h(20), h(40)) = 1 + max(1, 0) = 2
  New state: Same! h(20) didn't change.
 
AFTER INSERTION:
                30 [h=2, BF=+1]  ← BF changed from -1 to +1
               /  \
        20[h=1,BF=0]  40[h=0,BF=0]
         /  \
   10[h=0]  25[h=0]
 
Result: Tree remains balanced (all BFs in {-1, 0, +1})

Critical observation: Early termination

When propagating balance factor updates upward, we can often stop before reaching the root:

If a node's height doesn't change, no ancestors will change either. We can stop.
If a node's BF was +1 and becomes 0 (or -1 becomes 0), the subtree's height decreased, but the node absorbed the change. Ancestors won't see a height change.
If a node's BF was 0 and becomes ±1, the subtree's height increased. Continue propagating.
If a node's BF becomes ±2, we've found a violation. Handle it (via rotation), then potentially continue.

This early termination is crucial for efficiency—many insertions only affect a few nodes near the insertion point.

Deletion Is More Complex

Using Balance Factors for Violation Detection

The Four Imbalance Cases:

When BF(node) = +2 (left-heavy violation), we look at the left child's balance factor:

If BF(left child) ≥ 0: Left-Left (LL) case → Single right rotation
If BF(left child) < 0: Left-Right (LR) case → Double rotation (left then right)

When BF(node) = -2 (right-heavy violation), we look at the right child's balance factor:

If BF(right child) ≤ 0: Right-Right (RR) case → Single left rotation
If BF(right child) > 0: Right-Left (RL) case → Double rotation (right then left)

Imbalance Detection Using Balance Factors
Parent BF	Child BF	Case Name	Imbalance Shape	Fix
+2	≥ 0	Left-Left (LL)	Straight line left	Single right rotation
+2	< 0	Left-Right (LR)	Zig-zag left-right	Left rotation on child, then right rotation on parent
-2	≤ 0	Right-Right (RR)	Straight line right	Single left rotation
-2	0	Right-Left (RL)	Zig-zag right-left	Right rotation on child, then left rotation on parent

violation-detection.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type RotationType = 'LL' | 'LR' | 'RR' | 'RL' | 'BALANCED';
 
function detectViolationType<T>(node: AVLNode<T>): RotationType {
    const bf = getBalanceFactor(node);
    
    // No violation
    if (Math.abs(bf) <= 1) {
        return 'BALANCED';
    }
    
    // Left-heavy violation (BF = +2)
    if (bf > 1) {
        const leftBF = getBalanceFactor(node.left);
        // If left child is left-heavy or balanced: LL case
        // If left child is right-heavy: LR case
        return leftBF >= 0 ? 'LL' : 'LR';
    }
    
    // Right-heavy violation (BF = -2)
    if (bf < -1) {
        const rightBF = getBalanceFactor(node.right);
        // If right child is right-heavy or balanced: RR case
        // If right child is left-heavy: RL case
        return rightBF <= 0 ? 'RR' : 'RL';
    }
    
    return 'BALANCED';  // Should never reach here
}
 
// Complete rebalance function
function rebalance<T>(node: AVLNode<T>): AVLNode<T> {
    updateHeight(node);
    const violationType = detectViolationType(node);
    
    switch (violationType) {
        case 'LL':
            return rotateRight(node);
        case 'LR':
            node.left = rotateLeft(node.left!);
            return rotateRight(node);
        case 'RR':
            return rotateLeft(node);
        case 'RL':
            node.right = rotateRight(node.right!);
            return rotateLeft(node);
        default:
            return node;  // Already balanced
    }
}

The elegance of this approach:

Building a Mental Model for Balance Factors

To work effectively with AVL trees, you need to internalize how balance factors behave. Here are key mental models and patterns:

Mental Models for Balance Factors

•The Scale Analogy — Think of each node as a balance scale. The left subtree and right subtree are weights on either side. BF tells you which side is heavier and by how much. ±1 is a slight tilt (acceptable), ±2 is about to tip over (needs fixing).
•The Absorption Principle — When a subtree grows by 1, the parent node's BF changes by ±1. If the parent was already leaning the opposite way (e.g., was -1 and left subtree grew), the growth is 'absorbed' and the parent becomes balanced (BF = 0).
•The Propagation Limit — Height changes propagate up only when a node goes from BF=0 to BF=±1. If a node absorbs the change (±1 → 0), height doesn't change, and propagation stops.
•The Single Violation Rule (for Insertion) — An insertion can create at most one ±2 violation. Once fixed by rotation, the subtree's height is restored to its pre-insertion value, so ancestors are unaffected.
•The Direction Tells the Story — BF = +2 at node X means 'too many nodes on the left.' Look at X's left child Y to determine shape: if Y also leans left or is balanced (BF ≥ 0), it's a straight line (LL). If Y leans right (BF < 0), it's a zig-zag (LR).

Practice exercise: Trace insertions mentally

Given a sequence of insertions, practice predicting:

Where each node will be inserted (standard BST logic)
Which nodes will have their heights updated
Which nodes (if any) will have BF violations
What rotation type will be needed

This mental tracing builds the intuition that makes AVL trees feel natural rather than mysterious.

Debugging with Balance Factors

Common Misconceptions About Balance Factors

Balance factors are conceptually simple, but several misconceptions are common among those learning AVL trees. Let's address them directly:

Misconceptions to Avoid

•Misconception: BF tells you the node count difference — Wrong. BF = height(left) - height(right), not nodes(left) - nodes(right). A subtree with 100 nodes on the left and 50 nodes on the right might still have BF = 0 if both subtrees have the same height.
•Misconception: BF = 0 means equal subtree sizes — Wrong. A left subtree with nodes arranged as a perfect binary tree of height 3 (15 nodes) and a right subtree that's a straight line of height 3 (4 nodes) would both contribute height 3. BF = 0, but 15 ≠ 4.
•Misconception: A rotation always creates BF = 0 at the rotated node — Not always. After a single rotation, the new root might have BF = 0 or BF = ±1 depending on the original configuration. The key is that all BFs become valid (within ±1), not that they all become 0.
•Misconception: BF changes only for nodes on the insertion path — Mostly true, but subtly wrong. After a rotation, nodes involved in the rotation might change their parent-child relationships, affecting their heights and BFs. However, the affected region is still local.
•Misconception: BF = +2 always means 'rotate right' — Almost true for LL case, but wrong for LR case. When BF = +2 and the left child has BF < 0, you need a double rotation (left on child, then right on parent). The child's BF determines whether it's a straight-line or zig-zag imbalance.

The subtle point about node count vs. height:

Consider two subtrees:

Left: A complete binary tree with 7 nodes (height 2)
Right: A single chain of 3 nodes (height 2)

Both have height 2, so BF = 0. But the left has more than twice as many nodes!

Summary: The Balance Factor as Your Guide

The balance factor is a simple but powerful concept that underlies all AVL tree operations. Let's consolidate what we've learned:

Key Takeaways

•BF = height(left) - height(right) — The balance factor is the height difference between subtrees, with positive meaning left-heavy and negative meaning right-heavy.
•Valid BF values are -1, 0, +1 — Any other value indicates a violation of the AVL property that must be fixed by rotation.
•Store height, compute BF on demand — Most implementations store height at each node and derive BF when needed, simplifying code and debugging.
•Changes propagate upward — When we modify the tree, height and BF updates propagate from the modification point toward the root along the path.
•BF at violation point + BF of child determines rotation type — The combination of the violating node's BF (±2) and its heavy child's BF tells us exactly which of the four rotation cases applies.
•Early termination is possible — When a node absorbs a height change (BF goes toward 0), propagation stops because ancestors won't see any height change.

What's next:

Page Complete

2 / 4