//Implementation of Binary Tree
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
int data;
struct node *left;
struct node *right;
}node;
node *create()
node *p;
int x;
printf("Enter data(-1 for no data):");
scanf("%d",&x);
if(x==-1)
return NULL;
p=(node*)malloc(sizeof(node));
p->data=x;
printf("Enter left child of %d:\n",x);
p->left=create();
printf("Enter right child of %d:\n",x);
p->right=create();
return p;
void preorder(node *t) //address of root node is passed in t
if(t!=NULL)
printf("\n%d",t->data); //visit the root
preorder(t->left); //preorder traversal on left subtree
preorder(t->right); //preorder traversal om right subtree
void inorder(node *t) //address of root node is passed in t
if(t!=NULL)
inorder(t->left);
printf("\n%d",t->data); //preorder traversal on left subtree
inorder(t->right); //preorder traversal om right subtree
}
void postorder(node *t) //address of root node is passed in t
if(t!=NULL)
postorder(t->left);
postorder(t->right);
printf("\n%d",t->data); //preorder traversal om right subtree
int main()
node *root;
root=create();
printf("\nThe preorder traversal of tree is:\n");
preorder(root);
printf("\nThe Inorder traversal of tree is:\n");
inorder(root);
printf("\nThe Postorder traversal of tree is:\n");
postorder(root);
return 0;
}
//Implementation Of BST
#include <stdio.h>
#include <stdlib.h>
struct node
int data; //node will store an integer
struct node *right_child; // right child
struct node *left_child; // left child
};
void search(int i, struct node *n) {
if (n == NULL)
printf("\nValue does not exist in tree!");
else if(n->data == i)
printf("\nValue found!");
else if(i > n->data)
search(i, n->right_child);
else
search(i, n->left_child);
}
struct node* smallest(struct node *root)
while(root != NULL && root->left_child != NULL)
root = root->left_child;
//printf("\nSmallest value is %d\n", root->data);
return root;
struct node* largest(struct node *root)
while (root != NULL && root->right_child != NULL)
root = root->right_child;
// printf("\nLargest value is %d", root->data);
return root;
//function to create a node
struct node* new_node(int x)
struct node *p;
p = malloc(sizeof(struct node));
p->data = x;
p->left_child = NULL;
p->right_child = NULL;
return p;
struct node* insert(struct node *root, int x)
//searching for the place to insert
if(root==NULL)
return new_node(x);
else if(x>root->data) // x is greater. Should be inserted to right
root->right_child = insert(root->right_child, x);
else // x is smaller should be inserted to left
root->left_child = insert(root->left_child,x);
return root;
// funnction to delete a node
struct node* delete(struct node *root, int x)
//searching for the item to be deleted
if(root==NULL)
return NULL;
if (x>root->data)
root->right_child = delete(root->right_child, x);
else if(x<root->data)
root->left_child = delete(root->left_child, x);
else
//No Children
if(root->left_child==NULL && root->right_child==NULL)
free(root);
return NULL;
//One Child
else if(root->left_child==NULL || root->right_child==NULL)
struct node *temp;
if(root->left_child==NULL)
temp = root->right_child;
else
temp = root->left_child;
free(root);
return temp;
}
//Two Children
else
struct node *temp = smallest(root->right_child);
root->data = temp->data;
root->right_child = delete(root->right_child, temp->data);
return root;
void inorder(struct node *root)
if(root!=NULL) // checking if the root is not null
inorder(root->left_child); // visiting left child
printf(" %d ", root->data); // printing data at root
inorder(root->right_child);// visiting right child
int main()
{
/*
20
/ \
/ \
5 30
/ \ /\
/ \ / \
1 15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
struct node *root,*min,*max;
int x;
//struct node *min;
root = new_node(20);
insert(root,5);
insert(root,1);
insert(root,15);
insert(root,9);
insert(root,7);
insert(root,12);
insert(root,30);
insert(root,25);
insert(root,40);
insert(root, 45);
insert(root, 42);
inorder(root);
printf("\n");
root = delete(root, 1);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 40
/ \
/ \
9 45
/ \ /
/ \ /
7 12 42
*/
root = delete(root, 40);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 45
/ /
/ /
9 42
/ \
/ \
7 12
*/
root = delete(root, 45);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 42
/ \
/ \
7 12
*/
root = delete(root, 9);
inorder(root);
/*
20
/ \
/ \
5 30
\ /\
\ / \
15 25 42
/
/
12
*/
printf("\n");
min=smallest(root);
printf("\nSmallest value is %d\n", min->data);
max=largest(root);
printf("\nlargest value is %d\n", max->data);
printf("\n enetr element to search\n");
scanf("%d",&x);
search(x,root);
return 0;
