Tree rebalance(Tree t)
{
    if (t == NULL) return NULL;
    int n = TreeNumNodes(t); 
    if (n < 3) return t;
    // put node with median key at root
    t = partition(t, n/2);
    // then rebalance each subtree
    t->left = rebalance(t->left);
    t->right = rebalance(t->right);
    return t;
}