Header Ads Widget

Minimal Tree | Solution of cracking the coding interview

Rajnish Tripathi 20:53

 Problem:-

                 Given a sorted array with unique integer element , write an algorithm to create a binary search  tree with minimal height. 

Solution :-

#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left ,*right;
};

struct node *root=NULL;

// function for create createnode

struct node *createNode()
{
struct node *n;
n=new node;
return n;
}
void insert(int m)
{
node *temp,*t;
temp=createNode();
temp->data=m;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
root=temp;
else
{
t=root;
while(t!=NULL)
{
if(t->data>m)
{
if(t->left==NULL)
{
t->left=temp;
t=t->left;
}
t=t->left;
}
else
{
if(t->right==NULL)
{
t->right=temp;
t=t->right;
}
t=t->right;
}
}
}
}
void CreateBinarySearchTree(int *a,int l,int r)
{
if(l<=r)
{
int mid=(l+r)/2;
insert(a[mid]);
CreateBinarySearchTree(a,l,mid-1);
CreateBinarySearchTree(a,mid+1,r);
}
}

// function for preorder traversal

void preorder_traversal(struct node *temp)
{
if(temp)
{
printf("%d ",temp->data);
preorder_traversal(temp->left);
preorder_traversal(temp->right);
}
}

int main()
{
int arr[50];
int n;
cout<<"Enter the number of the element in the array"<<endl;
cin>>n;
cout<<"Enter the element in the array"<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
CreateBinarySearchTree(arr,0,n-1);
printf("Preorder traversal of the tree\n");
preorder_traversal(root);
return 0;
}



output:-

Enter the number of the element in the array
10
Enter the element in the array
1 3 5 6 11 12 13 14 23 34
Preorder traversal of the tree
11 3 1 5 6 14 12 13 23 34



Recommended Post:-

         MCQs:-

Tags:

Post a Comment

0 Comments