Binary Search Tree

Binary Search Tree

->  Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific order.

-> A binary search tree is a useful data structure for fast addition and removal of data.

-> It is composed of nodes, which stores data and also links to upto two other child nodes. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

-> In a binary search tree (BST), each node contains - 

1. Only smaller values in its left sub tree
2. Only larger values in its right sub tree

Example:

     

Consider the root node 20. All elements to the left of subtree(10, 5) are less than 20 and all elements to the right of subtree(25, 30, 35) are greater than 20.



// C program to implement Binary search Tree.

#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *left;
struct node *right;
}*root=NULL,*r;
struct node* addnode(struct node *r,int num)
{
if(r==NULL)
{
r=(struct node *)malloc(sizeof(struct node));
r->info=num;
r->left=NULL;
r->right=NULL;
}
else
if(num<r->info)
r->left=addnode(r->left,num);
else
r->right=addnode(r->right,num);
return r;
}
void create()
{
char ch;
int num;
do
{
printf("Enter a node:");
scanf("%d",&num);
root=addnode(root,num);
printf("Do you want to continue?");
scanf(" %c",&ch);
}while(ch=='Y'||ch=='y');
}
void inorder(struct node *r)
{
if(r!=NULL)

{
inorder(r->left);
printf("%d ",r->info);
inorder(r->right);
}
}

void preorder(struct node *r)
{
if(r!=NULL)

{
printf("%d ",r->info);
preorder(r->left);
preorder(r->right);
}
}

void postorder(struct node *r)
{
if(r!=NULL)

{
postorder(r->left);
postorder(r->right);
printf("%d ",r->info);

}
}

int main()
{
int ch;
do
{
printf("::::Binary search Tree::::\n");
printf("1.create 2.inorder 3.preorder 4.postorder 5.exit\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: create(); break;
case 2: inorder(root); break;
case 3: preorder(root); break;
case 4: postorder(root); break;
case 5: return 0;
default: printf("Invalid choice.."); 
        }
}while(ch!=5);
return 0;

}

OUTPUT:

::::Binary search Tree::::

1.create 2.inorder 3.preorder 4.postorder 5.exit

Enter your choice:1

Enter a node:20

Do you want to continue?y

Enter a node:10

Do you want to continue?y

Enter a node:30

Do you want to continue?y

Enter a node:5

Do you want to continue?y

Enter a node:25

Do you want to continue?y

Enter a node:35

Do you want to continue?n

::::Binary search Tree::::

1.create 2.inorder 3.preorder 4.postorder 5.exit

Enter your choice:2

5 10 20 25 30 35 

::::Binary search Tree::::

1.create 2.inorder 3.preorder 4.postorder 5.exit

Enter your choice:3

20 10 5 30 25 35 

::::Binary search Tree::::

1.create 2.inorder 3.preorder 4.postorder 5.exit

Enter your choice:4

5 10 25 35 30 20 

::::Binary search Tree::::

1.create 2.inorder 3.preorder 4.postorder 5.exit

Enter your choice:5

...