Binary search tree rotation

Question

I want to create an algorithm to sort binary search trees to make them balanced. But I can't do that If I don't understand myself how each step works!

So I have a binary search tree that I want to rotate to make it balanced. I already have and know the answer as shown by figure 2, but am unsure of the steps necessary to get to that point

Figure 1:

Figure 2:

Any pointers would be great.

Also I am using http://visualgo.net/bst.html

Answer 1

The thing you need here is called tree rotation

What you have done from step 1 to step 2 is a left rotation for node 16 like this:

Node 16 is imbalanced and size(left child) < size(right child) =>

1. We need to transfer the 16 node to left child,
2. Get a new node (the smallest) from the right child as the new node (18 since is the smallest)
3. Rebalance the right child