# How to balance a dangling node in an AVL tree

I have a sequence of numbers that are supposed to be placed into an AVL tree:

50, 22, 80, 70, 75, 73

I'm not sure where 73 goes. On my understanding the first balance happens when 75 becomes the right child of 70:

``````  50
/  \
22   80
/
70
\
75
``````

Thus, 80 is the "unbalanced" node and 70 is the heavy left child. So 70 moves to the left and 80 moves to the right, somehow, like this:

``````      50
/  \
22   75
/  \
70   80
``````

Adding 73, we become unbalanced yet again:

``````      50
/  \
22   75
/  \
70   80
\
73
``````

How do I balance this? I can't just put 73 between 75 and 70, can I?

What is being done to retain the AVL Property of trees is known as tree rotations. When it comes to AVL trees, we take a special attribute of nodes, in to consideration, named Balance Factor, which is the magnitude of the difference of the heights of the left and right sub trees for any node. For example, when `73` is added to your tree, balance factor for node `50` (written as `BF(50)` from now on) will become

``````BF(50) = | HeightLeft(50) - HeightRight(50) |
= | 1 - 3 |
= 2
``````

For a binary search tree to be an AVL tree, for each node `n` in the tree `BF(n)` should always be at most 1. Which means, once `73` is added, `BF(50)` becomes 2, hence the tree becomes unbalanced in terms of an AVL tree. Readjusting the tree to obtain the AVL property is done by performing rotations in the tree.

At once `73` is added, it would look like follows.

``````      50
/  \
22   75
/  \
70   80
\
73
``````

Rotate left from `73`, will give the follows.

``````      50
/  \
22   75
/  \
73   80
/
70
``````

Another rotation to right at `73` will give the follows.

``````      50
/  \
22   73
/  \
70   75
\
80
``````

Third rotation to left at `73` will give follows.

``````      73
/  \
50   75
/  \    \
22   70   80
``````

That's it. Now we have a balanced tree.

You could interpret the rotations as any of

• A left rotation followed by right-left double rotation
• A left-right double rotation followed by a left rotation

Read this for further knowledge on tree rotations to obtain balance.