Question

Write a binary search tree and include the functions to find the number of nodes and the height of the tree. Test your code in main. Print the post-order, in-order and pre-order traversal.

in c++ please.

Answer 1

Note: here all code are done as per your request in the question including comment details of each logic code, but if you have any doubt or issue feel free to ask me or post the issue.

BST.cpp

#include <iostream> 
using namespace std; 

class BST 
{ 
        int data; 
        BST *left, *right; 

        public: 
           // default constructor
                BST(){
                    data = 0;
                    left = NULL;
                    right = NULL;
            }
            
            // parameterized constructor
            BST(int value) { 
                data = value; 
                    left = right = NULL; 
            }  
        
               // Insert function. 
           BST* Insert(BST *root, int value) { 
                // Insert the first node, if root is NULL.
                if(!root) 
                    return new BST(value); 

                    //  Insert Right node data, if the 'value' is greater than 'root' node data.  
                if(value > root->data) 
                            root->right = Insert(root->right, value); 
                
                 //     Insert Left node data, if the 'value' is smaller than 'root' node data.
                    else
                            root->left = Insert(root->left, value); 
                return root; 
            } 
            
    int numOfNodes(BST* root){
        int count = 1;
    
        // if left is not null goto left node and increment count
        if (root->left != NULL) 
           count += numOfNodes(root->left);
    
           // if right is not null goto left node and increment count
        if (root->right != NULL) 
           count += numOfNodes(root->right);
    
        return count;
   }

    int height(BST* root){
        if(root == NULL)
             return 0;
    
        else { 
             // compute the depth of each subtree 
          int lDepth = height(root->left); 
          int rDepth = height(root->right); 
  
            // return  the max depth 
          if (lDepth > rDepth)  
            return(lDepth+1); 
          else return(rDepth+1); 
        }
    }
        
        // Preorder traversal. 
        void Preorder(BST *root){
            if(!root) 
           return; 
        
        cout << root->data << " "; 
        Inorder(root->left); 
        Inorder(root->right); 
    } 
        
        // Inorder traversal. 
        void Inorder(BST *root){
            if(!root) 
           return; 
        
        Inorder(root->left); 
        cout << root->data << " "; 
        Inorder(root->right); 
    } 
    
    // Postorder traversal. 
        void Postorder(BST *root){
            if(!root) 
           return; 
        
        Inorder(root->left); 
        Inorder(root->right);
    cout << root->data << " ";  
    } 
}; 


// Driver code 
int main() 
{ 
        BST b, *root = NULL; 
        int n;
/*      
        root = b.Insert(root, 50); 
        b.Insert(root, 30); 
        b.Insert(root, 20); 
        b.Insert(root, 40); 
        b.Insert(root, 70); 
        b.Insert(root, 60); 
        b.Insert(root, 80); 
*/      
        cout << "Enter size of n : ";
        cin >> n;
        for(int i=0; i<n; i++){
            int x;
            cin>>x;
            
            if(root == NULL)
           root = b.Insert(root, x); 
        else
           b.Insert(root, x);
    }
        
        int totalNodes = b.numOfNodes(root);
        cout << "Total Number of Nodes present in BST : " << totalNodes << endl;
        
        int ht = b.height(root);
        cout << "Height of BST : " << ht << endl;
        
   // Display BST
    cout << endl << "Display PreOrder BST : " << endl;
        b.Preorder(root);
    
    cout << endl << "Display InOrder BST : " << endl;
        b.Inorder(root);
    
    cout << endl << "Display PostOrder BST : " << endl;
        b.Postorder(root); 
        return 0; 
}