C++ program to convert a binary search tree to a Binary Tree














































C++ program to convert a binary search tree to a Binary Tree



Description:
The idea is to maintain a list of roots of all BSTs. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. 
Program:
#include <iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int key;
    struct node *left, *right;
};


struct node *newNode(int item)
{
    struct node *temp =  new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void preorder(struct node *root)
{
    if (root != NULL)
    {
        cout << root->key << " ";
        preorder(root->left);
        preorder(root->right);
    }
}
vector<struct node *> constructTrees(int start, int end)
{
    vector<struct node *> list;
    if (start > end)
    {
        list.push_back(NULL);
        return list;
    }
    for (int i = start; i <= end; i++)
    {
        vector<struct node *> leftSubtree  = constructTrees(start, i - 1);

        vector<struct node *> rightSubtree = constructTrees(i + 1, end);

        for (int j = 0; j < leftSubtree.size(); j++)
        {
            struct node* left = leftSubtree[j];
            for (int k = 0; k < rightSubtree.size(); k++)
            {
                struct node * right = rightSubtree[k];
                struct node * node = newNode(i);
                node->left = left;
                node->right = right;
                list.push_back(node);
            }
        }
    }
    return list;
}

int main()
{

    vector<struct node *> totalTreesFrom1toN = constructTrees(1, 3);
    cout << "Preorder traversals of all constructed BSTs are \n";
    for (int i = 0; i < totalTreesFrom1toN.size(); i++)
    {
        preorder(totalTreesFrom1toN[i]);
        cout << endl;
    }
    return 0;
}
Output:
Preorder traversals of all constructed BSTs are
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1

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 417 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