Untitled

void trav(TreeNode<int> *root,vector<int> &arr){ //get inorder array
    if(root==NULL) return;
    if(root->left) trav(root->left,arr);
    arr.push_back(root->data);
    if(root->right) trav(root->right,arr);
}

TreeNode<int>* make(vector<int> &arr,int s,int e){     //make BST from inorder array
    if(s>e) return NULL;  //dont add = as node maybe single
    int mid=s+(e-s)/2;
    TreeNode<int> * tmp =new TreeNode<int>(arr[mid]);
    tmp->left=make(arr,s,mid-1);
    tmp->right=make(arr,mid+1,e);
    return tmp;
}


TreeNode<int>* balancedBst(TreeNode<int>* root) {
    vector<int> arr;
    trav(root,arr);
    //now make BST from arr
    int size=arr.size();
    return make(arr,0,size-1);
}