Calculating Balance Factors
What you'll learn: You'll learn how to compute a node's balance factor—the key metric that determines whether an AVL tree is balanced at that node.
The Core Idea
A balance factor is simply a number that tells you how lopsided a node's subtrees are. For any node in a tree, you calculate it as:
Balance Factor = Height of Left Subtree - Height of Right Subtree
That's it! Subtract the right subtree's height from the left subtree's height.
Why It Matters
In AVL trees, we need to keep every node's balance factor within a safe range: -1, 0, or +1. This small calculation is what tells us whether we need to rebalance the tree.
- Balance Factor = 0: Both subtrees have equal height (perfectly balanced)
- Balance Factor = 1: Left subtree is one level taller (slightly left-heavy)
- Balance Factor = -1: Right subtree is one level taller (slightly right-heavy)
- Balance Factor > 1 or < -1: Violates AVL property—rebalancing needed!
Computing the Balance Factor
For a node with:
- Left subtree height = 3
- Right subtree height = 1
Balance Factor = 3 - 1 = 2 (too unbalanced!)
For a node with:
- Left subtree height = 2
- Right subtree height = 3
Balance Factor = 2 - 3 = -1 (acceptable)
Think of It Like a Seesaw
Imagine a seesaw where the left side is your left subtree and the right side is your right subtree. The balance factor measures how tilted the seesaw is. AVL trees only allow a gentle tilt—never a steep one.
Key Takeaway: The balance factor is the height difference between left and right subtrees (left minus right), and AVL trees require every node's balance factor to stay between -1 and +1 inclusive.