Top/Data structures/Trees/Balancing/Answer-balance-1

Answer to Question balance-1

Insertion using the basic algorithm yields the following tree. 
          10
         /  \
        /    \
       5     15
      /     /  \
     /     /    \
    2     12     20
     \
      \
       4
The first node above 4 that is out of balance is the node containing 5. Its left subtree has height 2 and its right subtree has height 0. Two steps down from that node toward the higher subtree involves a left step then a right step. So this is a zig-zag and calls for a double-rotation. The resulting tree is as follows. 
           10
          /  \
         /    \
        /      \
       4       15
      / \     /  \
     /   \   /    \
    2     5 12     20
The root (10) is already height-balanced, so this is the final tree.