// Implementation of Binary Search Tree operations in C

#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d -> ", root->key);
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node1, int key) {
// Return a new node if the tree is empty
if (node1 == NULL) return newNode(key);
 // Traverse to the right place and insert the node
if (key < node1->key)
node1->left = insert(node1->left, key);
else
node1->right = insert(node1->right, key);
return node1;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* searchNode(struct node* node1, int skey)
{
if (node1 == NULL || node1->key == skey) {
return node1;
}
if (node1->key < skey) {
return searchNode(node1->right, skey);
}
return searchNode(node1->left, skey);
}
// Deleting a node
struct node *deleteNode(struct node *node1, int dkey) {
if (node1 == NULL) return root; // Return if the tree is empty
if (dkey < node1->key) // Find the node to be deleted
node1->left = deleteNode(node1->left, dkey);
else if (dkey > node1->key)
node1->right = deleteNode(node1->right, dkey);
else { // If the node is with only one child or no child
if (node1->left == NULL) {
struct node *temp = node1->right;
free(node1);
return temp;
} else if (node1->right == NULL) {
struct node *temp = node1->left;
free(node1);
return temp;
}
// If the node has two children
struct node *temp = minValueNode(node1->right);
// Place the inorder successor in position of the node to be deleted
Node1->key = temp->key;
// Delete the inorder successor
Node1->right = deleteNode(node1->right, temp->key);
}
return node1;
}
 int main() {
struct node *root = NULL;
int arr[50],i,n,dkey,skey;
printf("\nEnter how many elements u want?:");
scanf("%d",&n);
printf("\nEnter %d elements into an array:",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
root = insert(root,arr[i]);
}
printf("Inorder traversal: ");
inorder(root);
printf("\nEnter element to search:");
scanf("%d",&skey);
if (searchNode(root, skey) != NULL) {
printf("\nkey is found\n");
}
else {
printf("\nkey is not found\n");
}
printf("\nEnter element to delete:");
scanf("%d",&dkey);
root = deleteNode(root, dkey);
printf("\n After deleting, Inorder traversal: ");
inorder(root);
}
// Implementation of Binary Search Tree Traversals with
recursion
#include <stdio.h>
struct tnode
{
int data;
struct tnode *right;
struct tnode *left;
};
struct tnode *CreateBST(struct tnode *, int);
void Inorder(struct tnode *);
void Preorder(struct tnode *);
void Postorder(struct tnode *);

int main()
{
struct tnode *root = NULL;
int arr[50],i,n,ele;
int choice, item;
do
{
printf("\n\nBinary Search Tree Operations\n");
printf("\n1. Creation of BST");
printf("\n2. Traverse in Inorder");
printf("\n3. Traverse in Preorder");
printf("\n4. Traverse in Postorder");
printf("\n5. Exit\n");
printf("\nEnter Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
root = NULL;
struct node *root = NULL;
printf("\nEnter how many elements u want?:");
scanf("%d",&n);
printf("\nEnter %d elements into an array:",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
root = CreateBST(root,arr[i]);
}
printf("\nBST with %d nodes is ready to Use!!\n", n);
break;
case 2:
printf("\nBST Traversal in INORDER \n");
Inorder(root);
break;
case 3:
printf("\nBST Traversal in PREORDER \n");
Preorder(root);
break;
case 4:
 printf("\nBST Traversal in POSTORDER \n");
Postorder(root);
break;
case 5:
printf("\n\n Terminating \n\n");
break;
default:
printf("\n\nInvalid Option !!! Try Again !! \n\n");
break;
}
} while(choice != 5);
return 0;
}

struct tnode *CreateBST(struct tnode *node1, int item)

{
if(node1 == NULL)
{
node1 = (struct tnode *)malloc(sizeof(struct tnode));
node1->left = node1->right = NULL;
node1->data = item;
return node1;
}
else
{
if(item < node1->data )
node1->left = CreateBST(node1->left,item);
 else if(item > node1->data )
node1->right = CreateBST(node1->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(node1);
}
}
void Inorder(struct tnode *root)
{
if( root != NULL)
{
Inorder(root->left);
printf(" %d ",root->data);
Inorder(root->right);
}
}

void Preorder(struct tnode *root)

{
if( root != NULL)
{
printf(" %d ",root->data);
Preorder(root->left);
Preorder(root->right);
}
}
void Postorder(struct tnode *root)
{
if( root != NULL)
{
Postorder(root->left);
Postorder(root->right);
printf(" %d ",root->data);
}
}
// Write a C program to count the no. of leaf nodes in a BST.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct tnode *CreateBST(struct tnode *node1, int item)
{
if(node1 == NULL)
{
node1 = (struct tnode *)malloc(sizeof(struct tnode));
node1->left = node1->right = NULL;
node1->data = item;
return node1;
}
else
{
if(item < node1->data )
node1->left = CreateBST(node1->left,item);
else if(item > node1->data )
node1->right = CreateBST(node1->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(node1);
}
}
int countLeaves(struct Node* node1) {
if (node1 == NULL) {
return 0;
}
// If the node has no left or right child, it is a leaf
if (node1->left == NULL && node1->right == NULL) {
return 1;
}
// Recursively count the leaves in the left and right subtrees
return countLeaves(node1->left)
+ countLeaves(node1->right);
}
int main() {
struct node *root = NULL;
printf("\nEnter how many elements u want?:");
scanf("%d",&n);
printf("\nEnter %d elements into an array:",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
root = CreateBST(root,arr[i]);
}
printf("\nNo. Of leaf nodes=%d\n", countLeaves(root));
return 0;
}
Write a C Program to find the height of a Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node* left, * right;
};
struct tnode *CreateBST(struct tnode *node1, int item)
{
if(node1 == NULL)
{
node1 = (struct tnode *)malloc(sizeof(struct tnode));
node1->left = node1->right = NULL;
node1->data = item;
return node1;
}
else
{
if(item < node1->data )
node1->left = CreateBST(node1->left,item);
else if(item > node1->data )
node1->right = CreateBST(node1->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(node1);
}
}
int maxHeight(struct node* node1)
{
if (node1 == NULL)
return -1;
else {
int lth = maxHeight(node1->left);
int rth = maxHeight(node1->right);
if (lth > rth)
return (lth+1);
else
return (rth + 1);
}
}
int main() {
struct node *root = NULL;
printf("\nEnter how many elements u want?:");
scanf("%d",&n);
printf("\nEnter %d elements into an array:",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
root = CreateBST(root,arr[i]);
}

printf("\nHeight of BST is:%d\n", maxHeight(root));

return 0;
}

Write a C Program to check whether the given BST is AVL or

not?
OR
Write a C program to check whether the given BST is Height
Balanced Tree or not?

#include <stdio.h>
#include <stdlib.h>
#define bool int
struct node {
int data;
struct node* left;
struct node* right;
};
int max(int a, int b) {
return (a >= b) ? a : b;
}
int height(struct node* node1) {
if (node1 == NULL)
return 0;
return 1 + max(height(node1->left), height(node1->right));
}
// Returns true if the tree is height-balanced
bool isBalanced(struct node* node1) {
int lh,rh;
if (node1 == NULL)
 return 1;
lh = height(node1->left);
rh = height(node1->right);
if (abs(lh - rh) <= 1 && isBalanced(node1->left) &&
isBalanced(node1->right))
return 1;
return 0;
}
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
struct node *insert(struct node *node1, int data) {
if (node == NULL) return newNode(data);
if (data < node1->data)
node1->left = insert(node1->left, data);
else
node1->right = insert(node1->right, data);
return node1;
}
int main() {
struct node *root = NULL;
int arr[50], i, n;
printf("Enter how many elements u want?: ");
scanf("%d", &n);
 printf("Enter %d elements into an array: ", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
root = insert(root, arr[i]);
}
if (isBalanced(root))
printf("\nTree is balanced");
else
printf("\nTree is not balanced");
getchar();
return 0;
}
Write a C Program to implement AVL tree.

#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *node1) {
if (node1 == NULL)
return 0;
return node1->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
struct Node *newNode(int key) {
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->key = key;
temp->left = NULL;
temp->right = NULL;
temp->height = 1;
return (temp);
}
// Right rotate
struct Node *rightRotate(struct Node *node1) {
struct Node *node2 = node1->left;
struct Node *T2 = node2->right;
node2->right = node1;
node1->left = T2;
node1->height = max(height(node1->left), height(node1->right)) + 1;
node2->height = max(height(node2->left), height(node2->right)) + 1;
return node2;
}
// Left rotate
struct Node *leftRotate(struct Node *node2) {
struct Node *node1 = node2->right;
struct Node *Temp = node1->left;

node1->left = node2;
node2->right = Temp;

node2->height = max(height(node2->left), height(node2->right)) + 1;

node1->height = max(height(node1->left), height(node1->right)) + 1;

return node1;
}

// Get the balance factor

int getBalance(struct Node *node1) {
 if (node1 == NULL)
return 0;
return height(node1->left) - height(node1->right);
}
struct Node *insertNode(struct Node *node1, int key) {
// Find the correct position to insertNode the node and insertNode it
if (node1 == NULL)
return (newNode(key));
if (key < node1->key)
node1->left = insertNode(node1->left, key);
else if (key > node1->key)
node1->right = insertNode(node1->right, key);
else
return node1;
// Update the balance factor of each node and Balance the tree
Node1->height = 1 + max(height(node1->left),
height(node1->right));
int balance = getBalance(node1);
if (balance > 1 && key < node1->left->key)
return rightRotate(node1);

if (balance < -1 && key > node1->right->key)

return leftRotate(node1);

if (balance > 1 && key > node1->left->key) {

node1->left = leftRotate(node1->left);
return rightRotate(node1);
 }

if (balance < -1 && key < node1->right->key) {

node1->right = rightRotate(node1->right);
return leftRotate(node1);
}
return node1;
}
struct Node *minValueNode(struct Node *node1) {
struct Node *current = node1;
while (current->left != NULL)
current = current->left;
return current;
}
// Delete a nodes
struct Node *deleteNode(struct Node *node1, int key) {
// Find the node and delete it
if (node1 == NULL)
return node1;

if (key < node1->key)

node1->left = deleteNode(node1->left, key);

else if (key > node1->key)

node1->right = deleteNode(node1->right, key);
else {
if ((node1->left == NULL) || (node1->right == NULL)) {
 struct Node *temp = node1->left ? node1->left : node1->right;

if (temp == NULL) {
temp = root;
root = NULL;
} else
*node1 = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(node1->right);
node1->key = temp->key;
node1->right = deleteNode(node1->right, temp->key);
}
}

if (node1 == NULL)
return node1;
// Update the balance factor of each node and balance the tree
Node1->height = 1 + max(height(node1->left),
height(node1->right));
int balance = getBalance(node1);
if (balance > 1 && getBalance(node1->left) >= 0)
return rightRotate(root);

if (balance > 1 && getBalance(root->left) < 0) {

root->left = leftRotate(root->left);
return rightRotate(node1);
 }

if (balance < -1 && getBalance(node1->right) <= 0)

return leftRotate(node1);

if (balance < -1 && getBalance(node1->right) > 0) {

node1->right = rightRotate(node1->right);
return leftRotate(node1);
}
return node1;
}
// Print the tree
void printPreOrder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->key);
printPreOrder(root->left);
printPreOrder(root->right);
}}

int main() {
struct Node *root = NULL;
int arr[50], i, n,dkey;
printf("Enter how many elements u want?: ");
scanf("%d", &n);
printf("Enter %d elements into an array: ", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
 root = insertNode(root, arr[i]);
}
printPreOrder(root);
printf(“\nEntet element to delete:”);
scanf(“%d”,&dkey);
root = deleteNode(root, dkey);
printf("\nAfter deletion: ");
printPreOrder(root);
return 0;
}