# A Binary Search Tree (BST)

Email
 Submitted on: 1/3/2015 9:29:00 PM By: Arati Rajbhandari Joshi (from psc cd) Level: Beginner User Rating: By 9 Users Compatibility: C, C++ (general), Borland C++ Views: 3512

This BST code will be useful to everyone who wants to know about the basic operations of a BST like Insertion, Deletion, Make Empty, Find Minimum, Find Maximun, Search, Traverse Ascending, and Traverse Descending. Do leave some comments on this code!!

code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
 ``` //************************************** // Name: A Binary Search Tree (BST) // Description:This BST code will be useful to everyone who wants to know about the basic operations of a BST like Insertion, Deletion, Make Empty, Find Minimum, Find Maximun, Search, Traverse Ascending, and Traverse Descending. Do leave some comments on this code!! // By: Arati Rajbhandari Joshi (from psc cd) //************************************** #include #include #include #include struct node{ int info; struct node *right; struct node *left; }; typedef struct node *BST; typedef struct node node; BST makeempty(BST t) { if (t!=NULL) { makeempty(t->left); makeempty(t->right); free(t); } return NULL; } BST find(BST t, int x) { if (t==NULL) return NULL; if (xinfo) return find(t->left,x); else if (x>t->info) return find(t->right,x); else return t; } BST findmin(BST t) { if(t==NULL) return NULL; else if(t->left==NULL) return t; else return findmin(t->left); } BST findmax(BST t) { if(t==NULL) return NULL; else if(t->right==NULL) return t; else return findmax(t->right); } BST insertnode(BST t, int x) { if(t==NULL) { t=(node*)malloc(sizeof(node)); if(t==NULL) printf("\n Out of Space !!"); else { t->info = x; t->left = t->right = NULL; } } else if (xinfo) { t->left=insertnode(t->left,x); } else if (x>t->info) { t->right=insertnode(t->right,x); } return t; } BST deletenode(BST t, int x) { BST tmpcell; if(t == NULL) { printf("\n Cannot Delete!! No Such Value Found"); } else if(x < t->info) t->left = deletenode(t->left,x); else if(x > t->info) t->right = deletenode(t->right,x); else if(t->right && t->left){ tmpcell = findmin(t->right); t->info = tmpcell->info; t->right = deletenode(t->right,tmpcell->info); } else { tmpcell = t; if(t->left == NULL) t = t->right; else if(t->right == NULL) t = t->left; free(tmpcell); printf("\n Value Successfully Deleted."); } return t; } void printtree_asc(BST t) { if (t!=NULL) { printtree_asc(t->left); printf("\n %d",t->info); printtree_asc(t->right); } } void printtree_desc(BST t) { if (t!=NULL) { printtree_desc(t->right); printf("\n %d",t->info); printtree_desc(t->left); } } main() { BST tree, pos; char ans; int val; tree=NULL; while(1){ printf(" Binary Search Tree (BST)"); printf("\n\n [1].\tInsert\n"); printf(" [2].\tDelete\n"); printf(" [3].\tMake Empty\n"); printf(" [4].\tFind Minimum\n"); printf(" [5].\tFind Maximun\n"); printf(" [6].\tSearch\n"); printf(" [7].\tPrint Ascending\n"); printf(" [8].\tPrint Descending\n"); printf(" [9].\tExit\n\n"); printf(" Enter Choice: "); ans = getche(); switch(ans) { case '1': { printf("\n Enter Value: "); scanf("%d",&val); tree=insertnode(tree,val); } break; case '2': { if(tree!=NULL) { printf("\n Enter Value to be Deleted: "); scanf("%d",&val); tree=deletenode(tree,val); } else printf("\n Cannot Delete!! Empty BST!!"); getch(); } break; case '3': { tree = makeempty(tree); printf("\n BST is now Empty!!"); getch(); } break; case '4': { pos=findmin(tree); if (pos!=NULL) printf("\n Minimum Value: %d",pos->info); else printf("\n Empty BST!! No Minimum Value."); getch(); } break; case '5': { pos=findmax(tree); if (pos!=NULL) printf("\n Maximum Value: %d",pos->info); else printf("\n Empty BST!! No Maximum Value."); getch(); } break; case '6': { if (tree!=NULL) { printf("\n Enter Value to be Searched: "); scanf("%d",&val); pos=find(tree, val); if (pos!=NULL) printf("\n %d is found in the BST",pos->info); else printf("\n %d not found in the BST",val); } else { printf("\n The BST is Empty!!"); } getch(); } break; case '7': { if(tree!=NULL) { clrscr(); printf("\n BST IN ASCENDING ORDER\n\n"); printtree_asc(tree); } else printf("\n Empty BST!!");; getch(); } break; case '8': { if(tree!=NULL) { clrscr(); printf("\n BST IN DESCENDING ORDER\n\n"); printtree_desc(tree); } else printf("\n Empty BST!!"); getch(); } break; case '9': exit(0); default : { printf("\n\n Choose from 1 to 9 only!!"); getch(); } break; } clrscr(); } } ```

Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Beginner category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)

Other User Comments

There are no comments on this submission.

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)

To post feedback, first please login.