Construct binary search tree by inserting the values in the order given

Introduction
In this article we are going to do a small assignment based on Binary  Search Tree.  We are going to create a binary tree by inserting the given values. Then in that tree we are performing operations like insert a new node , find the height of tree and minimum value element in tree. 

Problem Statement 

Construct binary search tree by inserting the values in the order given. After constructing a binary search tree ,
i.Insert new node
ii. Find number of nodes in longest path along with its height
iii. Minimum data value found in the tree 

 

Solution :

There are three rules for insertion of new node in binary tree : 
  1. Each node can have maximum of two child.
  2. If data to be inserted is less than data in root node then it is inserted in left side of the tree.
  3. If data to be inserted is greater than the data in root node then it is inserted in right side of the tree.
 
With these rules ,let's write C++ code for this task .

#Code for Creating Binary Search Tree and Operations on it 
Download the Code here

#include<iostream>

#include<math.h>

 using namespace std;

 class treeNode

{

 public:

    int data;

    treeNode *left;

    treeNode *right;

 public:

    treeNode *createNewNode(int val);

    void insertInTree(int val);

    int minimum();

    int height(treeNode *);

    void inorder(treeNode*);
   
   
};

treeNode *root = NULL;



 
int main()
{
    treeNode t;

    int choise ;

    int value,numberOfNodes;

    cout<<"Number of nodes present in Tree : ";

    cin>>numberOfNodes;

 
   for (int i = 0; i < numberOfNodes; i++)
    {
          cout<<"Enter the value : ";

          cin>>value;

          t.insertInTree(value);
    }

   
    do 
   {
        cout<<"\n\n\t\t\t________Operations on Binary Search Tree_________\n";

        cout<<"\n\t\t\t  1.Insert new node in Tree\n";

        cout<<"\t\t\t  2.Height of Binary Search Tree\n";

        cout<<"\t\t\t  3.Minimun value in Tree\n";

        cout<<"\t\t\t  4.Inorder Traversal\n";

        cout<<"\t\t\t  5.Exit\n";

        cout<<"Your choise : ";

        cin>>choise;

        switch(choise)
    {
            case 1:
                   {
                        cout<<"Enter the value : ";

                        cin>>value;

                        t.insertInTree(value);
                  }
            break;

            case 2:
                         cout<<"The height of Tree is : "<<t.height(root)<<endl;
            break;

            case 3:
                       cout<<"The minimum value in the tree is :                            "<<t.minimum()<<endl;
            break;
        
             case 4:
       
                          cout<<"Inorder Traversal is : \n";
                
                          t.inorder(root);

            break;
           
        }

    }while(choise<5&&choise>0);


}



treeNode *treeNode:: createNewNode(int val)
{
  
  treeNode *temp = new treeNode;
  
  temp->data = val;
  
  temp->left = NULL;
  
  temp->right = NULL;
   
   return temp;
}void treeNode :: insertInTree(int val)
{
    treeNode *parent ,*current = root;

    if(root==NULL)
    {
        root = createNewNode(val);
    }
 
   
else
     {
 
        while(current!=NULL)
        {
 
            parent = current;
           if (val<current->data)
 
               current = current->left;
           else 

                if (val>current->data)
 
               current = current->right;
        }

 
        if (val<parent->data)
 
            parent->left = createNewNode(val);
 
        else
 
            if (val>parent->data)
 
                parent->right = createNewNode(val);
    }

}int treeNode :: minimum()
{
        treeNode *temp = root;

        while(temp->left!=NULL)
 
            temp = temp->left;
 
        return temp->data;

}int treeNode:: height(treeNode *Root)
{
 
    treeNode *current = Root;
 
    if (current == NULL)
    {
 
        return 0;
    }
 
   
else
     {
 
        int h = max(height(current->left),height(current->right));
 
        return h+1;
    }
}void treeNode :: inorder(treeNode *Root)
{
 
    treeNode *temp= Root;
 
    if (temp==NULL)
 
        return;
 
    inorder(temp->left);
 
    cout<<"\t"<<temp->data;

    inorder(temp->right);
}

Note :  This code is successfully compiled and run under Linux distribution Ubuntu 18.04 LTS environment .   

Output :

 $ g++ createBinaryTree.cpp
$ ./a.out 

 Number of nodes present in Tree : 5
Enter the value : 20
Enter the value : 10
Enter the value : 30
Enter the value : 5
Enter the value : 40


            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Height of Binary Search Tree
            3.Minimun value in Tree
            4.Inorder Traversal
            5.Exit
Your choise : 4
Inorder Traversal is :
    5    10    20    30    40

            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Height of Binary Search Tree
            3.Minimun value in Tree
            4.Inorder Traversal
            5.Exit
Your choise : 1
Enter the value : 14


            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Height of Binary Search Tree
            3.Minimun value in Tree
            4.Inorder Traversal
            5.Exit
Your choise : 4
Inorder Traversal is :
    5    10    14    20    30    40

            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Height of Binary Search Tree
            3.Minimun value in Tree
            4.Inorder Traversal
            5.Exit
Your choise : 2
The height of Tree is : 3


            ________Operations on Binary Search Tree_________

            1.Insert new node in Tree
            2.Height of Binary Search Tree
            3.Minimun value in Tree
            4.Inorder Traversal
            5.Exit
Your choise : 3
The minimum value in the tree is : 5