C++ Program to Implement Binary Search Tree

«
»
This C++ Program demonstrates operations on Binary Search Tree

Here is source code of the C++ Program to demonstrate Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program To Implement BST
  3.  */
  4. # include <iostream>
  5. # include <cstdlib>
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.     int info;
  13.     struct node *left;
  14.     struct node *right;
  15. }*root;
  16.  
  17. /*
  18.  * Class Declaration
  19.  */
  20. class BST
  21. {
  22.     public:
  23.         void find(int, node **, node **);    
  24.         void insert(node *, node *);
  25.         void del(int);
  26.         void case_a(node *,node *);
  27.         void case_b(node *,node *);
  28.         void case_c(node *,node *);
  29.         void preorder(node *);
  30.         void inorder(node *);
  31.         void postorder(node *);
  32.         void display(node *, int);
  33.         BST()
  34.         {
  35.             root = NULL;
  36.         }
  37. };
  38. /*
  39.  * Main Contains Menu
  40.  */
  41. int main()
  42. {
  43.     int choice, num;
  44.     BST bst;
  45.     node *temp;
  46.     while (1)
  47.     {
  48.         cout<<"-----------------"<<endl;
  49.         cout<<"Operations on BST"<<endl;
  50.         cout<<"-----------------"<<endl;
  51.         cout<<"1.Insert Element "<<endl;
  52.         cout<<"2.Delete Element "<<endl;
  53.         cout<<"3.Inorder Traversal"<<endl;
  54.         cout<<"4.Preorder Traversal"<<endl;
  55.         cout<<"5.Postorder Traversal"<<endl;
  56.         cout<<"6.Display"<<endl;
  57.         cout<<"7.Quit"<<endl;
  58.         cout<<"Enter your choice : ";
  59.         cin>>choice;
  60.         switch(choice)
  61.         {
  62.         case 1:
  63.             temp = new node;
  64.             cout<<"Enter the number to be inserted : ";
  65. 	    cin>>temp->info;
  66.             bst.insert(root, temp);
  67.         case 2:
  68.             if (root == NULL)
  69.             {
  70.                 cout<<"Tree is empty, nothing to delete"<<endl;
  71.                 continue;
  72.             }
  73.             cout<<"Enter the number to be deleted : ";
  74.             cin>>num;
  75.             bst.del(num);
  76.             break;
  77.         case 3:
  78.             cout<<"Inorder Traversal of BST:"<<endl;
  79.             bst.inorder(root);
  80.             cout<<endl;
  81.             break;
  82. 	case 4:
  83.             cout<<"Preorder Traversal of BST:"<<endl;
  84.             bst.preorder(root);
  85.             cout<<endl;
  86.             break;
  87.         case 5:
  88.             cout<<"Postorder Traversal of BST:"<<endl;
  89.             bst.postorder(root);
  90.             cout<<endl;
  91.             break;
  92.         case 6:
  93.             cout<<"Display BST:"<<endl;
  94.             bst.display(root,1);
  95.             cout<<endl;
  96.             break;
  97.         case 7:
  98.             exit(1);
  99.         default:
  100.             cout<<"Wrong choice"<<endl;
  101.         }
  102.     }
  103. }
  104.  
  105. /*
  106.  * Find Element in the Tree
  107.  */
  108. void BST::find(int item, node **par, node **loc)
  109. {
  110.     node *ptr, *ptrsave;
  111.     if (root == NULL)
  112.     {
  113.         *loc = NULL;
  114.         *par = NULL;
  115.         return;
  116.     }
  117.     if (item == root->info)
  118.     {
  119.         *loc = root;
  120.         *par = NULL;
  121.         return;
  122.     }
  123.     if (item < root->info)
  124.         ptr = root->left;
  125.     else
  126.         ptr = root->right;
  127.     ptrsave = root;
  128.     while (ptr != NULL)
  129.     {
  130.         if (item == ptr->info)
  131.         {
  132.             *loc = ptr;
  133.             *par = ptrsave;
  134.             return;
  135.         }
  136.         ptrsave = ptr;
  137.         if (item < ptr->info)
  138.             ptr = ptr->left;
  139. 	else
  140. 	    ptr = ptr->right;
  141.     }
  142.     *loc = NULL;
  143.     *par = ptrsave;
  144. }
  145.  
  146. /*
  147.  * Inserting Element into the Tree
  148.  */
  149. void BST::insert(node *tree, node *newnode)
  150. {
  151.     if (root == NULL)
  152.     {
  153.         root = new node;
  154.         root->info = newnode->info;
  155.         root->left = NULL;
  156.         root->right = NULL;
  157.         cout<<"Root Node is Added"<<endl;
  158.         return;
  159.     }
  160.     if (tree->info == newnode->info)
  161.     {
  162.         cout<<"Element already in the tree"<<endl;
  163.         return;
  164.     }
  165.     if (tree->info > newnode->info)
  166.     {
  167.         if (tree->left != NULL)
  168.         {
  169.             insert(tree->left, newnode);	
  170. 	}
  171. 	else
  172. 	{
  173.             tree->left = newnode;
  174.             (tree->left)->left = NULL;
  175.             (tree->left)->right = NULL;
  176.             cout<<"Node Added To Left"<<endl;
  177.             return;
  178.         }
  179.     }
  180.     else
  181.     {
  182.         if (tree->right != NULL)
  183.         {
  184.             insert(tree->right, newnode);
  185.         }
  186.         else
  187.         {
  188.             tree->right = newnode;
  189.             (tree->right)->left = NULL;
  190.             (tree->right)->right = NULL;
  191.             cout<<"Node Added To Right"<<endl;
  192.             return;
  193.         }	
  194.     }
  195. }
  196.  
  197. /*
  198.  * Delete Element from the tree
  199.  */
  200. void BST::del(int item)
  201. {
  202.     node *parent, *location;
  203.     if (root == NULL)
  204.     {
  205.         cout<<"Tree empty"<<endl;
  206.         return;
  207.     }
  208.     find(item, &parent, &location);
  209.     if (location == NULL)
  210.     {
  211.         cout<<"Item not present in tree"<<endl;
  212.         return;
  213.     }
  214.     if (location->left == NULL && location->right == NULL)
  215.         case_a(parent, location);
  216.     if (location->left != NULL && location->right == NULL)
  217.         case_b(parent, location);
  218.     if (location->left == NULL && location->right != NULL)
  219.         case_b(parent, location);
  220.     if (location->left != NULL && location->right != NULL)
  221.         case_c(parent, location);
  222.     free(location);
  223. }
  224.  
  225. /*
  226.  * Case A
  227.  */
  228. void BST::case_a(node *par, node *loc )
  229. {
  230.     if (par == NULL)
  231.     {
  232.         root = NULL;
  233.     }
  234.     else
  235.     {
  236.         if (loc == par->left)
  237.             par->left = NULL;
  238.         else
  239.             par->right = NULL;
  240.     }
  241. }
  242.  
  243. /*
  244.  * Case B
  245.  */
  246. void BST::case_b(node *par, node *loc)
  247. {
  248.     node *child;
  249.     if (loc->left != NULL)
  250.         child = loc->left;
  251.     else
  252.         child = loc->right;
  253.     if (par == NULL)
  254.     {
  255.         root = child;
  256.     }
  257.     else
  258.     {
  259.         if (loc == par->left)
  260.             par->left = child;
  261.         else
  262.             par->right = child;
  263.     }
  264. }
  265.  
  266. /*
  267.  * Case C
  268.  */
  269. void BST::case_c(node *par, node *loc)
  270. {
  271.     node *ptr, *ptrsave, *suc, *parsuc;
  272.     ptrsave = loc;
  273.     ptr = loc->right;
  274.     while (ptr->left != NULL)
  275.     {
  276.         ptrsave = ptr;
  277.         ptr = ptr->left;
  278.     }
  279.     suc = ptr;
  280.     parsuc = ptrsave;
  281.     if (suc->left == NULL && suc->right == NULL)
  282.         case_a(parsuc, suc);
  283.     else
  284.         case_b(parsuc, suc);
  285.     if (par == NULL)
  286.     {
  287.         root = suc;
  288.     }
  289.     else
  290.     {
  291.         if (loc == par->left)
  292.             par->left = suc;
  293.         else
  294.             par->right = suc;
  295.     }
  296.     suc->left = loc->left;
  297.     suc->right = loc->right;
  298. }
  299.  
  300. /*
  301.  * Pre Order Traversal
  302.  */
  303. void BST::preorder(node *ptr)
  304. {
  305.     if (root == NULL)
  306.     {
  307.         cout<<"Tree is empty"<<endl;
  308.         return;
  309.     }
  310.     if (ptr != NULL)
  311.     {
  312.         cout<<ptr->info<<"  ";
  313.         preorder(ptr->left);
  314.         preorder(ptr->right);
  315.     }
  316. }
  317. /*
  318.  * In Order Traversal
  319.  */
  320. void BST::inorder(node *ptr)
  321. {
  322.     if (root == NULL)
  323.     {
  324.         cout<<"Tree is empty"<<endl;
  325.         return;
  326.     }
  327.     if (ptr != NULL)
  328.     {
  329.         inorder(ptr->left);
  330.         cout<<ptr->info<<"  ";
  331.         inorder(ptr->right);
  332.     }
  333. }
  334.  
  335. /*
  336.  * Postorder Traversal
  337.  */
  338. void BST::postorder(node *ptr)
  339. {
  340.     if (root == NULL)
  341.     {
  342.         cout<<"Tree is empty"<<endl;
  343.         return;
  344.     }
  345.     if (ptr != NULL)
  346.     {
  347.         postorder(ptr->left);
  348.         postorder(ptr->right);
  349.         cout<<ptr->info<<"  ";
  350.     }
  351. }
  352.  
  353. /*
  354.  * Display Tree Structure
  355.  */
  356. void BST::display(node *ptr, int level)
  357. {
  358.     int i;
  359.     if (ptr != NULL)
  360.     {
  361.         display(ptr->right, level+1);
  362.         cout<<endl;
  363.         if (ptr == root)
  364.             cout<<"Root->:  ";
  365.         else
  366.         {
  367.             for (i = 0;i < level;i++)
  368.                 cout<<"       ";
  369. 	}
  370.         cout<<ptr->info;
  371.         display(ptr->left, level+1);
  372.     }
  373. }

advertisement
$ g++ bst.cpp
$ a.out
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 8
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
Root->:  8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 9
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              9
Root->:  8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              9
Root->:  8
              5
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
              5
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 3 
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
                            10
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 2
Enter the number to be deleted : 10
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     11
              9
Root->:  8
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 3
Inorder Traversal of BST:
3  5  7  8  9  11  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 4
Preorder Traversal of BST:
8  5  3  7  9  11  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 5
Postorder Traversal of BST:
3  7  5  11  9  8  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 2
Enter the number to be deleted : 8
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              11
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 15
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     15
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 4
Preorder Traversal of BST:
9  5  3  7  11  10  15  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 5
Postorder Traversal of BST:
3  7  5  10  15  11  9  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
 
                     15
              11
                     10
Root->:  9
                     7
              5
                     3
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Delete Element 
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 7
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.