Program to create a Binary Search Tree

Binary Search Trees: 

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

1. The left subtree of the root contains keys smaller than the root.
2. The right subtree of the root contains keys greater than the root.
3. The left and right subtrees are also Binary Search Trees.
4. There are no duplicates in the tree.

Program to create a Binary Search Tree:

/*Creating a Binary Search Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct binarytree
{int info;
struct binarytree *left;
struct binarytree *right;
}BT;

BT *create()
{BT *temp=(BT *)malloc(sizeof(BT));
if(temp==NULL)
{printf(“nMemory Allocation Error.”);
exit(1);
}
return temp;
}

BT *makenode(int x)
{BT *ptr=create();
ptr->info=x;
ptr->left=NULL;
ptr->right=NULL;
return ptr;
}

BT *insert(BT *root,int x)
{BT *p,*q,*ptr=makenode(x);
if(root==NULL)
{root=ptr;
return root;
}
p=q=root;
while(p!=NULL)
{q=p;
if(x<q->info)
p=q->left;
else
p=q->right;
}
if(x<q->info)
q->left=ptr;
else
q->right=ptr;
return root;
}

void inorder(BT *root)
{if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

void preorder(BT *root)
{if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

void postorder(BT *root)
{if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info); }
}

void main()
{
BT *root=NULL;
int ch,x;
while(1)
{clrscr();
printf(“nBinary Search Tree-MENU”);
printf(“nn1. Insert Node”);
printf(“n2. Inorder Display”);
printf(“n3. Preorder Display”);
printf(“n4. Postorder Display”);
printf(“n5. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number?”);
scanf(“%d”,&x);
root=insert(root,x);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
postorder(root);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice.”);
}
getch();
}
}