C++ Data Structures and Algorithms

Rotating nodes

The balanced BST can be achieved if the difference of the node's left height and the node's right height is no more than 1. Please see the following mathematical notation:

|GetHeight(node->Left) - GetHeight(node->Right)| ≤ 1

Based on the preceding notation, we can initialize the balance variable with the following code:

int balance =     GetHeight(node->Left) - GetHeight(node->Right);

If balance == 2 then the tree is left heavy and we need to rotate the left subtree. In contrast, if balance == -2 then the tree is right heavy and we need to rotate the right subtree. Please see the following diagram:

In the preceding diagram, we ...