Normal BST to Balanced BST

 #include<bits/stdc++.h>

using namespace std;

#define shailesh ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define int long long int

#define vi vector<int>

#define pii pair<int, int>

#define vii vector<pii>

#define rep(i, a, b) for(int i=a; i<b; i++)

#define ff first

#define ss second

const int N=1e5+10;

bool isPowerOfTwo(int x){

     return x&&(!(x&(x-1)));

}

bool isPrime(int n)

{

    if (n <= 1)

    return false;

    if (n <= 3)

    return true;

    if (n % 2 == 0 || n % 3 == 0)

    return false;

    for (int i = 5; i * i <= n; i = i + 6)

    if (n % i == 0 || n % (i + 2) == 0)

    return false;

    return true;

}

bool isPalindrome(string S)

{

    for (int i = 0; i < S.length() / 2; i++) {

        if (S[i] != S[S.length() - i - 1]) {

        return false;

        }

    }

 return true;

}

struct Node{

    int data;

    struct Node* left;

    struct Node* right;

    Node(int val){

        data=val;

        left=NULL;

        right=NULL;

    }

};

void StoreBSTNode(Node* root, vector<Node*> &v){

    if(!root) return;

   

    StoreBSTNode(root->left, v);

    v.push_back(root);

    StoreBSTNode(root->right, v);

   

}

Node* BuildTree(vector<Node*> &v, int start, int end){

    if(start>end){

        return NULL;

    }

     int mid=(start+end)/2;

     Node* root=v[mid];

     root->left= BuildTree(v, start, mid-1);

     root->right=BuildTree(v, mid+1, end);

     return root;

}

Node* build(Node* root){

    vector<Node*> v;

    StoreBSTNode(root, v);

    int n=v.size();

    return BuildTree(v, 0, n-1);

}

void preOrder(Node* node)

{

    if (node == NULL)

        return;

    printf("%d ", node->data);

    preOrder(node->left);

    preOrder(node->right);

}

signed main(){

   shailesh

    #ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

   

    struct Node* root=new Node(10);

    root->left=new Node(8);

    root->left->left=new Node(7);

    root->left->left->left=new Node(6);

    root->left->left->left->left=new Node(5);

   

    root=build(root);

   

   preOrder(root);

   

return 0;

}