Binary Search Tree Operations

#include<stdio.h>
#include<malloc.h>//dynamic memory allocation
#include <limits.h>//to use INT_MAX and INT_MIN

//node structure
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}node;

//creating a single node
node* createNode(int data){
node* newNode=(node*)malloc(sizeof(node));
newNode->data=data;
newNode->left=newNode->right=NULL;
return newNode;
}

//inserting a node into BST
node* insert(node* root,int data){
if(root==NULL)
return createNode(data);
if(root->data < data)
root->right= insert(root->right,data);
else
root->left= insert(root->left,data);
return root;
}

//Search
node* search(node *root,int key){
if(root==NULL || root->data==key)
return root;
if(root->data<key)
return search(root->right,key);
return search(root->left,key);
}

//create a Binary Search Tree
node* createBST(){
node* root=insert(NULL,15);
root=insert(root,10);
root=insert(root,4);
root=insert(root,12);
root=insert(root,22);
root=insert(root,18);
root=insert(root,24);
return root;
}

//Finding height of BST
int heightOfBST(node* root){
if(root==NULL)
return 0;
int lheight=heightOfBST(root->left);
int rheight=heightOfBST(root->right);
if(lheight>rheight)
return(lheight+1);
return(rheight+1);
}

//Printing elements of given level
void printGivenLevel(node* root,int level){
if(root==NULL)
return;
if(level==1)
printf("%d ",root->data);
printGivenLevel(root->left,level-1);
printGivenLevel(root->right,level-1);
}

//Level order traversal of BST
void levelOrderPrint(node* root){
int i,height=heightOfBST(root);
if(root==NULL)
return;
for(i=1;i<=height;i++){
printGivenLevel(root,i);
printf("\n");
}

}

//find Successor
node* findSuccessor(node* root,int key){
node* temp;
if(root==NULL)
return NULL;
if(root->data==key){
if(root->right==NULL)
return NULL;
temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
return temp;
}
if(root->data<key)
return findSuccessor(root->right,key);
return findSuccessor(root->left,key);
}

//Finding Minimum value in the BST
int findMinValue(node* root){
node *temp=root;
while(temp->left!=NULL)
temp=temp->left;
return temp->data;
}

//Finding Maximum value in the BST
int findMaxValue(node *root){
node *temp=root;
while(temp->right!=NULL)
temp=temp->right;
return temp->data;
}

//isBST wrong implementation
int isBST(node *root){
if(root==NULL)
return 1;
if(root->left!=NULL && root->left->data >root->data)
return 0;
if(root->right!=NULL && root->right->data <root->data)
return 0;
return isBST(root->right)&&isBST(root->left);
}

//isBST right but not efficient
int isBST2(node *root){
if(root==NULL)
return 1;
if(root->left!=NULL && findMaxValue(root->left) >root->data)
return 0;
if(root->right!=NULL && findMinValue(root->right)<root->data)
return 0;
return isBST(root->right)&&isBST(root->left);
}

//isBST right and efficient
int isBST3(node* root,int min,int max){
if(root==NULL)
return 1;
if(root->data <min || root->data >max)
return 0;
return isBST3(root->left,min,root->data)&&isBST3(root->right,root->data,max);
}

//lowest common ancestor
node* findLca(node *root,int n1,int n2){
if(root==NULL)
return NULL;
if(root->data>n1 && root->data>n2)
return findLca(root->left,n1,n2);
if(root->data<n1&&root->data<n2)
return findLca(root->right,n1,n2);
return root;
}

//driver
int main1(){
//Declaration
node *root=createBST(),*temp;
int data,input2;
//level order traversal
levelOrderPrint(root);

//finding successor
/*printf("Enter : ");
scanf("%d",&data);
temp=findSuccessor(root,data);
printf("\Result is %d\n",temp==NULL?-1:temp->data);*/

//search
/*printf("Enter : ");
scanf("%d",&data);
temp=search(root,data);
printf("\Result is %d\n",temp==NULL?-1:temp->data);*/

//min and max value
//printf("\nMin Value : %d\nMax Value : %d\n",findMinValue(root),findMaxValue(root));

//IsBST
/*printf("IsBST : %d\n",isBST2(root));
printf("IsBST : %d\n",isBST3(root,INT_MIN,INT_MAX));
root->left->right->right=createNode(16);
levelOrderPrint(root);
printf("IsBST : %d\n",isBST2(root));
printf("IsBST : %d\n",isBST3(root,INT_MIN,INT_MAX));*/

//lca
printf("Enter number to find lca : ");
scanf("%d%d",&data,&input2);
temp=findLca(root,data,input2);
printf("\Result is %d\n",temp==NULL?-1:temp->data);
return 0;
}