Balancing a binary search tree

This is a problem and a solution that I thought of while reading about binary search trees which have the property that each node has at most two children and all the nodes in the left sub-tree of a node are always less than or equal to the considered node and the ones in the right subtree are always greater than the considered node.

The problem basically arises when the tree is unbalanced. The search times in worst cases go by the order of the height of the tree and a badly balanced tree can cause bad search times. The question primarily asks, given a BST, how can we give a balanced version of that BST?


How did I approach the question?

I first felt that we needed a in-order traversal of the tree. An in-order traversal gives the nodes in increasing order. Obviously, it would be great if the median can be the new root. For each subtree, using the in-order traversal, we can recalculate a balanced version recursively.

The primary recurrence uses as input the nodes of the tree put into an array in in-order. For a subtree from index i to j, the root would be the mid of i and j and it's left subtree would come from the same recurrence from i to mid and the right subtree from mid + q to j.

Here is the method:

node balance(int min, int max,node[] arr) {
if(min == max)
return arr[min];
int mid = (min + max )/2;
node curr = arr[mid];
curr.left = balance(min, mid-1, arr);
curr.right = balance(mid + 1, max, arr);
return curr;
}

Here is the git link.