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. }

$ 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.

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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.