/* In place BT to BST conversion , complexity quadratic time . any suggestions to improve it to nlogn time ? quicksort techinique wont work , niether will heapsort [cause heap is a almost complete binary tree structure , so thats where it gets its speed , from besided parent pointer would i think require extra space to be maintained , any modified heap technique ?? or any other ideas how to do this even if it takes same time or more time , also recursion is using space equivalent to number of nodes anyways , so dont see the point .. but discussion is good...  */


node * maxTree(node * root)
{
    node * leftmax , *rightmax , *curmax;
    if(root == NULL)
        return NULL;
    curmax = root;
    leftmax = maxTree(root->left);
    rightmax = maxTree(root->right);
    if ( leftmax )
        leftmax->data > curmax->data ? ( curmax = leftmax ) :  curmax ;
    if ( rightmax )
        rightmax->data > curmax->data ? (curmax = rightmax ) : curmax;

    return curmax;
}

node * minTree(node * root)
{
    node * leftmin , *rightmin , *curmin;
    if(root == NULL)
        return NULL;
    curmin = root;
    leftmin = minTree(root->left);
    rightmin = minTree(root->right);
    if ( leftmin )
        leftmin->data < curmin->data ? ( curmin = leftmin ) :  curmin ;
    if ( rightmin )
        rightmin->data < curmin->data ? (curmin = rightmin ) : curmin ;

    return curmin;
}





void bin2bst(node * root)
{
    int temp;  // data type in tree
    if(root == NULL)
        return ;
    node * leftT , *rightT ;
    lefT = maxTree(root->left);
    righT = minTree(root->right);
    if (leftT != NULL && left->data > root->data){
        temp = leftT->data;
        leftT->data = root->data;
        root->data = temp;
    }

    if(rightT !=NULL && right -> data < root->data ){
        temp = rightT->data;
        rightT->data = root->data;
        root->data = temp;
    }

    bin2bst(root->left);
    bin2bst(root->right);
}