Balance Factor

  • Identify the height and balance factor of binary search tree nodes.

To assist in establishing balance property, we define the following measure:

Each node's balance factor is the height of the left subtree minus the height of the right subtree.

More specifically

bf(node) = height(node.left) – height(node.right)

For the calculation of balance factor, we define "height" as follows:

$$ \text{height}(n)=\left \{ \begin{matrix} -1 & n = \text{null} \\ 0 & n = \text{leaf} \\ 1 + \max(\text{height of children}) & n \neq \text{leaf} \end{matrix} \right \} $$

A BST is balanced when, for any node, its balance factor is $1$, $0$, or $-1$.

Here is an example

The above BST is not balanced because $\text{bf}(\{ 10, 5 \})\notin \{0, 1, -1 \}$.