C++ program to convert binary tree to binary search tree














































C++ program to convert binary tree to binary search tree



Description:
1.Copy the items of binary tree in a set while doing inorder traversal. This takes O(n log n) time. Note that set in C++ STL is implemented using a Self Balancing Binary Search Tree.

2.There is no need to sort the set as sets in C++ are implemented using Self-balancing binary search trees.

3.Now simply copy the items of set one by one from beginning to the tree while doing inorder traversal of tree. Care should be taken as when copying each item of set from its beginning, we first copy it to the tree while doing inorder traversal, then remove it from the set as well.
Program:
#include<iostream>
#include <bits/stdc++.h>
using namespace std;

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

void storeinorderInSet(Node* root, set<int>& s)
{
    if (!root)
        return;


    storeinorderInSet(root->left, s);
    s.insert(root->data);
    storeinorderInSet(root->right, s);

}
void setToBST(set<int>& s, Node* root)
{

    if (!root)
        return;
    setToBST(s, root->left);
    auto it = s.begin();
    root->data = *it;
    s.erase(it);
    setToBST(s, root->right);

}
void binaryTreeToBST(Node* root)
{
    set<int> s;
    storeinorderInSet(root, s);
    setToBST(s, root);

}
Node* newNode(int data)
{

    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}


void inorder(Node* root)
{
    if (!root)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(5);
    root->right->left = newNode(8);
    root->left->left = newNode(9);
    root->left->right = newNode(11);
    root->right->right = newNode(43);


    binaryTreeToBST(root);
    cout << "Inorder traversal of BST is: " << endl;
    inorder(root);
    return 0;
}

Output:
Inorder traversal of BST is: 1 2 5 8 9 11 43  

More Articles of MAYANK KUMAR:

Name Views Likes
C++ program to remove all leaf nodes from the binary search tree 347 18
C++ program to find K%u2019th largest element in binary search tree when tree modification is not allowed 375 22
C++ program to find K%u2019th smallest element in binary search tree 356 24
C++ program to find second largest element in binary search tree 341 17
C++ program to find K%u2019th largest element in binary search tree 342 19
C++ program to check if each internal node of a binary search tree has exactly one child 319 12
C++ program to reverse a path in binary search tree using queue 347 19
C++ program to check if a binary tree is binary search tree or not 360 15
C++ program to find lowest Common Ancestor in a binary search tree 360 19
C++ program to binary Tree to binary search tree Conversion using std::Set 335 13
C++ program to merge Two binary search trees 367 17
C++ program to construct binary search tree from its given level order traversal 458 29
C++ program to convert a binary search tree to a Binary Tree 416 26
Difference between binary tree and binary search tree 432 26
C++ program to construct binary search tree from given inorder traversal 446 19
C++ program to convert binary tree to binary search tree 567 19
C++ Program to Print String 350 18
C++ Program to List Files in Directory 377 21
C++ Program to Delete Files 283 15
C++ Program to Get IP Address 384 24
C++ Program to Print Date and Time 331 11
C++ Program to Copy Files 338 19
C++ Program to Write to File 319 20
C++ Program to Read a File 322 19
C++ Program to Swap Two Variables 315 15
C++ Program to Find Largest of Two Number 373 20
C++ Program to Print Prime Numbers 364 20
C++ Program to Find Square Root of Number 322 15
C++ Program to Calculate Grade of Student 328 23
C++ Program to Calculate Average of Numbers 348 14
C++ Program to Calculate Average Percentage 298 15
C++ Program to Add Subtract Multiply Divide 324 24
C++ Program to Add Two Numbers 354 16
C++ Program to Get Input from User 310 18
C++ Program to Check Whether a String is Palindrome or Not 283 11
C++ Program to Find LCM 264 11
C++ Program to Convert Decimal to Binary Using Recursion 294 14
C++ Program to Find Factorial of Number Using Recursion 305 17
C++ Program to Find Sum of Natural Numbers Using Recursion 359 29
C++ Program to Find HCF or GCD 317 17
C++ Program to Find ASCII Value of Character 291 18
C++ Program to Find Numbers Divisible by Another Number 437 18
C++ Program to Find the Sum of Natural Numbers 270 17
C++ Program to convert Celsius to Fahrenheit 268 16
C++ Program to Check if a Number is Positive, Negative or 0 315 20
C++ Program to find square root of a number 294 19
C++ program for counting sort Algorithm 281 17
C++ programs for Bucket sort Algorithm 253 14
C++ program for Bubble sort 325 15

Comments