Program to delete duplicates from a link list
Cracking the Coding interview

Minimal Tree | Solution of cracking the coding interview

Rajnish

Problem (Minimal Tree | Solution of cracking the coding interview):-

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

Solution (Minimal Tree | Solution of cracking the coding interview) :-

#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:-

Leave a Reply

Your email address will not be published.