Problem Statement

Given a Binary Tree, convert it to Binary Search Tree in such a way that keeps the original structure of Binary Tree intact.

Example 1:

Input:
      1
    /   \\
   2     3
Output:1 2 3

Example 2:

Input:
          1
       /    \\
     2       3
   /
 4
Output:1 2 3 4
Explanation:
The converted BST will be

        3
      /   \\
    2     4
  /
 1

Expected Time Complexity: O(NLogN).

Expected Auxiliary Space: O(N).

Problem Link

Binary Tree to BST | Practice | GeeksforGeeks

Code

class Solution{
  public:
    // The given root is the root of the Binary Tree
    // Return the root of the generated BST
    vector<int> nodes;
    void inorder(Node *root)
    {
        if(!root)
        return;
        
        inorder(root->left);
        nodes.push_back(root->data);
        inorder(root->right);
        
    }
    Node *formBST(int &head,int n)
    {
        if(n<=0)
        return NULL;
        
        Node *lst = formBST(head,n/2);
        
        Node *root = new Node(nodes[head]);
        
        root->left = lst;
        
        head++;
        
        Node *rst = formBST(head,n-n/2-1);
        
        root->right = rst;
        
        return root;
    }
    Node *binaryTreeToBST (Node *root)
    {
        inorder(root); // Step 1: Store the inorder traversal of the BT to a vector
        
        sort(nodes.begin(),nodes.end());// Step 2: Sort that vector
        
        int n = nodes.size();
        int head = 0;
        
        return formBST(head,n);// Step 3: Form BST from a sorted array
    }
};