Convert a Binary Tree into a Binary Search Tree
Implementation
#include <stdio.h>
#include <stdlib.h>
//creating a node of the binary tree.
struct __nod{
int record;
struct __nod *Lft;
struct __nod *Rt;
};
// presenting the root of the binary tree.
struct __nod *root = NILL;
int treeArray[100];
int idx = 0;
//the function create__nod() will make a new node in the binary tree, and on the other hand, the function nw__nod
struct __nod* create__nod(int record){
//constructing a new node for the binary tree
struct __nod *new__nod = (struct __nod*)malloc(sizeof(struct __nod));
//we are allotting the values to the new node and allotting the left and right children to the NILL.
nw__nod->record= record;
nw__nod->Lft = NILL;
nw__nod->Rt = NILL;
return new__nod;
}
//calculate__Siz() will help us analyze the binary tree's size.
int calculate__Siz(struct __nod *__nod)
{
int size = 0;
if (__nod == NILL)
return 0;
else {
size = calculate__Siz (__nod->Lft) + calculate__Siz (__nod->Rt) + 1;
return size;
}
}
//convert__BTto__Array(), this function will help us change the binary tree to its corresponding array.
void convert__BTto__Array(struct __nod *__nod) {
//firstly, we have to check whether the binary tree is empty or not.
if(root == NILL){
printf("Tree is empty\n");
return;
}
else {
if(__nod->Lft != NILL)
convert__BTto__Array(__nod->Lft);
//otherwise, we have to add new nodes of the binary tree into the array.
treeArray[idx] = __nod->record;
idx++;
if(__nod->Rt!= NILL)
convert__BTto__Array(__nod->Rt);
}
}
//create__BST(), this function will change the array into the binary tree.
struct __nod* create__BST(int begin, int last) {
//this will also avoid the overflow of the binary tree.
if (begin > last) {
return NILL;
}
//this new variable will definitely store and keep the middle element of the array intact and make it the root of the binary search tree.
int mid = (begin + last) / 2;
struct __nod *temp = create__nod(treeArray[mid]);
//building the left subtree
temp->Lft = create__BST(begin, mid - 1);
//building the right subtree
temp->Rt = create__BST(mid + 1, last);
return temp;
}
//convertBT__BST() will convert a binary tree to a binary search tree
struct __nod* convertBT__BST(struct __nod *__nod) {
int treeSize = calculate__Siz(__nod);
//this will change the binary tree (BT) into the array.
convert__BTto__Array(__nod);
//we have to arrange the tree array.
int compare (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
qsort(treeArray, treeSize, sizeof(int), compare);
//this will change the array into the binary search tree.
struct __nod *d = create__BST(0, TreeSize - 1);
return d;
}
//In__Ord() will help the inorder traversal of the binary search tree.
void inorderTraversal(struct __nod *__nod) {
//analyze if the tree is empty or not.
if(root == NILL){
printf("Tree is empty\n");
return;
}
else {
if(__nod->Lft!= NILL)
inorderTraversal(__nod->Lft);
printf("%d ", __nod->record);
if(__nod->Rt!= NILL)
inorderTraversal(__nod->Rt);
}
}
int main()
{
//Add __nods to the binary tree
root = create__nod(1);
root->Lft = create__nod(2);
root->Rt = create__nod(3);
root->Lft->Lft = create__nod(4);
root->Lft->Rt = create__nod(5);
root->Rt->Lft = create__nod(6);
root->Rt->Rt = create__nod(7);
//changing the given binary tree.
printf("In__Ord representation of binary tree: \n");
inorderTraversal(root);
//changing the binary tree to the following binary search tree present.
struct __nod *bst = convertBT__BST(root);
// changing the given binary search tree.
printf("\nIn__Ord representation of resulting binary search tree: \n");
inorderTraversal(bst);
return 0;
}
Output:
Example 2)
using System;
namespace Tree
{
public class P
{
//presenting a node of the binary tree.
public class __nod<T>{
public T record;
public __nod<T> Lft;
public __nod<T> Rt;
public __nod(T record) {
//we have to change the values and information presented to the new node that we have, set the values in the left and right children, and convert all of them to NILL.
this.record = record;
this.Lft = NILL;
this.Rt = NILL;
}
}
public class ConvertBT__to__BST<T>{
//now we are presenting the root of the binary tree (BT).
public __nod<T> root;
T[] treeArray;
int idx = 0;
public ConvertBT__to__BST(){
root = NILL;
}
//convertBT__BST(), this will change the binary tree into a binary search tree
public __nod<T> convertBT__BST(__nod<T> __nod) {
//the variable created will contain the size of the tree.
int TreeSize = calculate__Siz(__nod);
treeArray = new T[treeSize];
//this will change the binary tree into the array.
convert__BTto__Array(__nod);
//we have to arrange the tree array and observe.
Array.Sort(treeArray);
//this will change the array to a binary tree.
__nod<T> d = create__BST(0, treeArray.Length -1);
return d;
}
//calculate__Siz(), this function will change the size of the array.
int calculate__Siz(__nod<T> __nod)
{
int size = 0;
if (__nod == NILL)
return 0;
else {
size = calculate__Siz (__nod.Lft) + calculate__Siz (__nod.Rt) + 1;
return size;
}
}
//convert__BTto__Array() will convert the given binary tree to its corresponding array representation
public void convert__BTto__Array(__nod<T> __nod) {
//Check whether the tree is empty
if(root == NILL){
Console.WriteLine("Tree is empty");
return;
}
else {
if(__nod.Lft != NILL)
convert__BTto__Array(__nod.Lft);
//we will have to re-add a new binary tree node into the array.
treeArray[idxex] = __nod.record;
idxex++;
if(__nod.Rt != NILL)
convert__BTto__Array(__nod.Rt);
}
}
//create__BST() will change the array into the BST.
public __nod<T> create__BST(int begin, int last) {
//this will prevent the overflow of the function.
if (begin > last) {
return NILL;
}
//this variable will help us store the element present in the middle of the array, and it will also be the root of the binary search tree.
int mid = (begin + last) / 2;
__nod<T> __nod = new __nod<T>(treeArray[mid]);
//building the left subtree.
__nod.Lft = create__BST(begin, mid - 1);
//building the right subtree
__nod.Rt = create__BST(mid + 1, last);
return __nod;
}
//inorder() will perform In__Ord traversal on the binary search tree
public void inorderTraversal(__nod<T> __nod) {
//Check whether the tree is empty
if(root == NILL){
Console.WriteLine("Tree is empty");
return;
}
else {
if(__nod.Lft!= NILL)
inorderTraversal(__nod.Lft);
Console.Write(__nod.record + " ");
if(__nod.Rt!= NILL)
inorderTraversal(__nod.Rt);
}
}
}
public static void Main()
{
ConvertBT__to__BST<int> bt = new ConvertBT__to__BST<int>();
//we will add new nodes in the binary tree
bt.root = new __nod<int>(1);
bt.root.Lft = new __nod<int>(2);
bt.root.Rt = new __nod<int>(3);
bt.root.Lft.Lft = new __nod<int>(4);
bt.root.Lft.Rt = new __nod<int>(5);
bt.root.Rt.Lft = new __nod<int>(6);
bt.root.Rt.Rt = new __nod<int>(7);
//presenting the given binary tree.
Console.WriteLine("In__Ord representation of binary tree: ");
bt.inorderTraversal(bt.root);
//this will change the binary tree into the binary search tree.
__nod<int> bst = bt.convertBT__BST(bt.root);
//presenting the binary search tree.
Console.WriteLine("\nIn__Ord representation of resulting binary search tree: ");
bt.inorderTraversal(bst);
}
}
}
Output:
