Binary search Tree Implementation and Traversal

Binary Search Tree and Operations

/******* BST Tree and Operations **********/
#include <stdio.h>
#include <stdlib.h>struct Node {
int key;
struct Node* left;
struct Node* right;
};

struct Node *root=NULL,*temp=NULL;

struct Node* createNode(int key) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;

}

struct Node* insert(struct Node* node, int key) {
// Base case: if the tree is empty, create a new node
if (node == NULL) {
    return createNode(key);
    }

// Compare the key with the current node's key
if (key < node->key) {
// Recursively insert into the left subtree
    node->left = insert(node->left, key);
    } else if (key > node->key) {

// Recursively insert into the right subtree
   node->right = insert(node->right, key);
}
// Return the modified node
return node;
}

void inOrderTraversal(struct Node* node) {
if (node != NULL) {
// Traverse the left subtree
inOrderTraversal(node->left);
// Visit the current node
printf("%d---",node->key);
// Traverse the right subtree
inOrderTraversal(node->right);
}
}

void preOrderTraversal(struct Node* node) {
if (node != NULL) {
// Visit the current node
printf("%d---",node->key);
// Traverse the left subtree
preOrderTraversal(node->left);
// Traverse the right subtree
preOrderTraversal(node->right);
}
}

void postOrderTraversal(struct Node* node) {
if (node != NULL) {
// Traverse the left subtree
postOrderTraversal(node->left);
// Traverse the right subtree
postOrderTraversal(node->right);
// Visit the current node
printf("%d---",node->key);
}
}

struct Node* search(struct Node* root, int key) {
// Base cases: the key is not present or the root is null
if (root == NULL || root->key == key) {
return root;
}

// Key is smaller than the root's key, search in the left subtree
if (key < root->key) {
return search(root->left, key);
}
// Key is greater than the root's key, search in the right subtree
return search(root->right, key);
}

int findMinimum(struct Node* root) {
// Base case: the leftmost leaf node contains the minimum value
while (root->left != NULL) {
root = root->left;
}
return root->key;
}

int findMaximum(struct Node* root) {
// Base case: the rightmost leaf node contains the maximum value
while (root->right != NULL) {
root = root->right;
}
return root->key;
}

struct Node* inordersucc(struct Node* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}

// Function to delete a key from a BST

struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL) {
  return root;
   }
if (key < root->key) {
   root->left = deleteNode(root->left, key);
} else if (key > root->key) {
root->right = deleteNode(root->right, key);
} 

else {
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;

} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

struct Node* temp = inordersucc(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}

int main()

{
int op,key;
do
{
printf("\n.menu\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.search\n7.Minimum\n8.Maximum\n9.exit\nenter option\n");
scanf("%d",&op);
switch(op)
{
case 1:printf("Enter the key:");
            scanf("%d",&key);
            if (root==NULL)
                root=insert(root,key);
            else
            insert(root,key);
            break;
case 2:printf("Preorder Traversal\n");
           preOrderTraversal(root);
           break;
case 3:printf("Postorder Traversal\n");
           postOrderTraversal(root);
            break;
case 4:
           printf("Inorder traversal\n");
           inOrderTraversal(root);
           break;
case 5:
    printf("Enter the key to delete:");
    scanf("%d",&key);
    root = deleteNode(root, key);
    printf("In-Order Traversal after deleting %d: ", key);
    inOrderTraversal(root);
    break;
case 6:
    printf("Enter the key to search:");
    scanf("%d",&key);
    temp=search(root,key);
    if (temp==NULL)
        printf("Key not Found \n");
    else
        printf("key found \n");
    break;
case 7:printf("Minimum key element is =%d\n",findMinimum(root));
           break;
case 8:printf("Maximum key element is =%d\n",findMaximum(root));
            break;
}
}
while(op!=9);
return 0;
}

/*********************** non recursive implementation ****************/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
struct node
{
int data;
struct node *lchild;
struct node *rchild;
}*root=NULL;
typedef struct node Node;
void insert()
{
Node *t;
t=(Node *)malloc(sizeof(Node));
printf("Enter data....");
scanf("%d",&t->data);
t->lchild=NULL;
t->rchild=NULL;


if(root==NULL) root=t;
else
{
Node *pre,*cur;
cur=root;
while(1)
{
if(t->data<cur->data) { pre=cur;cur=cur->lchild;if(cur==NULL) {pre->lchild=t;break;}}
else if(t->data>cur->data){ pre=cur;cur=cur->rchild;if(cur==NULL) {pre->rchild=t;break;}}
else { printf("Invalid Input");exit(0);}
}
}
}


void search()
{ int key;
int f=0;
int nc=0;
printf("Enter key to serach...");
scanf("%d",&key);
Node *cur=root;

while(cur!=NULL)
{ nc++;
if(cur->data==key) {f=1;break;}

if(key<cur->data) cur=cur->lchild;
else if(key>cur->data) cur=cur->rchild;

}
if(f)printf("Keyfound!!! number of comaprisons %d",nc);else printf("key Not found...");
}
void inorder(Node *r)
{


if(r!=NULL)
{


inorder(r->lchild);
printf("<--> %d",r->data);
inorder(r->rchild);
}
}
void preorder(Node *r)
{
if(r!=NULL)
{
printf("<--> %d",r->data);
preorder(r->lchild);
preorder(r->rchild);
}
}
void postorder(Node *r)
{
if(r!=NULL)
{
preorder(r->lchild);
preorder(r->rchild);
printf("<-->%d",r->data);
}
}
Node* insuc(Node *r)
{
Node *q=NULL;
while(r->lchild!=NULL)
{
q=r; r=r->lchild;
}
if(r->rchild!=NULL) q->lchild=r->rchild;else q->lchild=NULL;
return(r);
}
void delete()
{
printf("Enter key to delete...");
int d;
scanf("%d",&d);
Node *cur=root;
int f=0;
Node *pr=NULL;
while(cur!=NULL)
{
if(cur->data==d) {f=1;break;}

if(d<cur->data) {pr=cur; cur=cur->lchild;}
else if(d>cur->data){pr=cur; cur=cur->rchild;}
}
if(f==0) printf("key not found..!!!");
else
{
Node *t=cur;// node to be deleted...
//leaf nodes....
if(t->lchild==NULL&&t->rchild==NULL)
{
if(pr->lchild==t) pr->lchild=NULL;
if(pr->rchild==t) pr->rchild=NULL;
}
else if(t->lchild==NULL) // only right child exist
{
if(pr->lchild==t) pr->lchild=t->rchild;
if(pr->rchild==t) pr->rchild=t->rchild;
}

else if(t->rchild==NULL) // only left child exist
{
if(pr->lchild==t) pr->lchild=t->lchild;
if(pr->rchild==t) pr->rchild=t->lchild;
}
else //both left and right child
{
Node *in=t->rchild;
if(in->lchild==NULL) {t->data=in->data;t->rchild=in->rchild;}
else {in=insuc(t->rchild);t->data=in->data;}
}

}//end of found else
}// end of delete fn


int main()
{int op;
do
{
printf("\n.menu\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.search\n7.exit\nenter option\n");
scanf("%d",&op);
switch(op)
{
case 1:insert();break;
case 2:preorder(root);break;
case 3:postorder(root);break;
case 4:inorder(root);break;
case 5:delete();break;
case 6:search();break;
}
}
while(op!=7);
}