Balance Factor

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

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 \} $$

Here is an example

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