Binary Search Trees: Convert Binary Tree into Binary Search Tree.

Example

Input:
          11
         /  \
        3    8
       / \
      9   5

Output:
          9
         /  \
        5    11
       / \
      3   8

Solution

The solution is simple:

1. Take the node values into an temp array by doing inorder traversal of the tree.

2. Then sort the array

3. Then do an inorder traversal of the sorted array, You will get BST.

Because in a BST if you do an inorder traversal, you will get the values in sorted order.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};
 


Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 
  
void store_inorder(Node* root, set<int> &Set)
{
    // base case
    if (root == nullptr) {
        return;
    }
 
    store_inorder(root->left, Set);
    Set.insert(root->data);
    store_inorder(root->right, Set);
}

void convert_to_BST(Node* root, set<int>::iterator &it)
{
    if (root == nullptr) {
        return;
    }
 
    convert_to_BST(root->left, it);
 
    root->data = *it;
    it++;
 
    convert_to_BST(root->right, it);
}

int main()
{
    Node* root = get_new_node(10);
    root->left = get_new_node(2);
    root->right = get_new_node(1);
    root->left->left = get_new_node(5);
    root->left->right = get_new_node(4);
    root->right->left = get_new_node(8);
    root->right->right = get_new_node(6);
 
    // store the node data into a set inorder fashion
    // as we are using set, it will store the values in sorted order.
    set<int> set;
    store_inorder(root, set);
 
    // Now, put back the keys by using the BST function
    auto it = set.begin();
    convert_to_BST(root, it);
 
    // print the BST
    print_inorder(root);

    return 0;
}

Output:

1 2 4 5 6 8 10