The Balance Factor

To measure balance, we start from height, which we defined in the tree chapter. The height of a node is the number of edges on the longest path from that node down to a leaf. A leaf has height $0$, because it has no children. The empty tree, a null child, has height $-1$. We use $-1$ so that the recursive formula gives the correct height for a leaf:

$$\text{height}(node)=1+\max (\text{height}(left),\text{height}(right))$$

Balance is about how the heights of a node’s two subtrees compare. If they are the same height, the node is balanced. If one is taller, the node is heavy on that side.

Here is a balanced node:

       ╭───╮
       │ 5 │
       ╰─┬─╯
    ┌────┴─────┐
  ╭─┴─╮      ╭─┴─╮
  │ 3 │      │ 7 │
  ╰───╯      ╰───╯

Both subtrees of 5 are single leaves of height $0$.

Now here is a node that is heavy on one side:

    ╭───╮
    │ 7 │
    ╰─┬─╯
    ┌─┘
  ╭─┴─╮
  │ 5 │
  ╰─┬─╯
  ┌─┘
╭─┴─╮
│ 3 │
╰───╯

The left subtree of 7 has height $1$, and its right subtree is empty, with height $-1$. The gap between them is $1-(-1)=2$. That gap is what we call the balance factor of a node: the height of its left subtree minus the height of its right subtree.

$$\text{bf}(node)=\text{height}(left)-\text{height}(right)$$

The sign tells us which side is heavy. A positive balance factor means the left side is taller, so the node is left-heavy. A negative one means the right side is taller, so the node is right-heavy. A balance factor of $0$ means the two sides are the same height, so the node is balanced.

So 5 above has $\text{bf}=0$. Here is the mirror image of the tree under 7. Its root is right-heavy:

╭───╮
│ 3 │
╰─┬─╯
  └─┐
  ╭─┴─╮
  │ 5 │
  ╰─┬─╯
    └─┐
    ╭─┴─╮
    │ 7 │
    ╰───╯

The left subtree of 3 is empty and its right subtree has height $1$, so $\text{bf}=-1-1=-2$.