bst cpp

#include<iostream>

using namespace std;

class node{
    protected:
        int element;
        node* left;
        node* right;

    public:

        //constructor that accepts only element
        node(int element){
            this->element = element;
            this->left = NULL;
            this->right = NULL;
        }

        //constructor that accepts element, left Link, Right Link
        node(int element, node* leftLink, node* rightLink){
            this->element = element;
            this->left = leftLink;
            this->right = rightLink;
        }

        //method to update data of the node
        void updateData(int element){
            this->element = element;
        }

        //method to update the left Link of the node
        void updateLeftLink(node* temp){
            this->left = temp;
        }

        //method to update the right link of the node
        void updateRightLink(node* temp){
            this->right = temp;
        }

        //method that returns the element of the node
        int getElement(){
            return this->element;
        }

        //method that returns left Link
        node* getLeftNode(){
            return this->left;
        }

        //method that returns the right Link
        node* getRightNode(){
            return this->right;
        }
};

//binary search tree class
class BST{
    protected:
        node* root;

    public:

        //constructor for bst
        BST(){
            root = NULL;
        }

        //returns true if the root node is null
        bool isEmpty(){
            return(root == NULL);
        }

        //returns root node
        node* getRoot(){
            return root;
        }

        void insert(int element){
            node* temp = new node(element);
            //if tree is empty put it at root node
            if(root == NULL){
                root = temp;
            }
            else{
                bool inserted = false;
                //creating a node pointer to traverse the tree
                node* p = root;

                //keep looping while the node is not inserted
                while(not inserted){
                    //if element of the new node is less than the current node than insert it to the left
                    if(p->getElement() > temp->getElement()){
                        if(p->getLeftNode() == NULL){
                            p->updateLeftLink(temp);
                            inserted = true;
                        }
                        else{
                            p = p->getLeftNode();
                        }
                    }
                    //if element of the new node is greater than the current node than insert it to the right
                    else if(p->getElement() < temp->getElement()){
                        if(p->getRightNode() == NULL){
                            p->updateRightLink(temp);
                            inserted = true;
                        }
                        else{
                            p = p->getRightNode();
                        }
                    }
                }
            }
        }

        // method to delete a element from the bst
        // initially tempNode is assigned as the root node
        bool deleteElement(int element,node* tempNode){

            static bool removed = false;
            static node* parent;
            int data = 0;
            if(tempNode == NULL){
                return false;
            }
            data = tempNode->getElement();

            // if data is less than the node data then traverse left
            if(data > element){
                parent = tempNode;
                tempNode = tempNode->getLeftNode();
                deleteElement(element,tempNode);
            }
            // if data greater than the node data then traverse right
            if(data < element){
                parent = tempNode;
                tempNode = tempNode->getRightNode();
                deleteElement(element,tempNode);
            }
            // if data is equal to the node data
            if(data == element){

                // deleting a leaf node
                if(tempNode->getLeftNode() == NULL && tempNode->getRightNode() == NULL){

                    if(parent->getElement() > tempNode->getElement()){
                        parent->updateLeftLink(NULL);
                    }

                    else if(parent->getElement() < tempNode->getElement()){
                        parent->updateRightLink(NULL);
                    }
                    delete tempNode;
                }

                // deleting a node with left subtree
                else if(tempNode->getLeftNode() != NULL && tempNode->getRightNode() == NULL){

                    if(parent->getElement() > tempNode->getElement()){
                        parent->updateLeftLink(tempNode->getLeftNode());
                    }

                    else if(parent->getElement() < tempNode->getElement()){
                        parent->updateRightLink(tempNode->getLeftNode());
                    }
                    delete tempNode;
                }

                // deleting a node with right subtree
                else if(tempNode->getLeftNode() == NULL && tempNode->getRightNode() != NULL){
                    if(parent->getElement() > tempNode->getElement()){
                        parent->updateLeftLink(tempNode->getRightNode());
                    }

                    else if(parent->getElement() < tempNode->getElement()){
                        parent->updateRightLink(tempNode->getRightNode());
                    }
                    delete tempNode;
                }

                //deleting root node
                else if(tempNode->getLeftNode() != NULL && tempNode->getRightNode() != NULL && tempNode->getElement() == root->getElement()){

                    node* q = tempNode->getLeftNode();
                    node* r = tempNode->getRightNode();
                    root = r;
                    while(r->getLeftNode()!= NULL){
                        r = r->getLeftNode();
                    }
                    r->updateLeftLink(q);
                    delete tempNode;
                }

                // deleting a node with both left and right subtree
                else if(tempNode->getLeftNode() != NULL && tempNode->getRightNode() != NULL){

                    if(parent->getElement() > tempNode->getElement()){
                        parent->updateLeftLink(tempNode->getRightNode());
                    }

                    else if(parent->getElement() < tempNode->getElement()){
                        parent->updateRightLink(tempNode->getRightNode());
                    }

                    node* q = tempNode->getLeftNode();
                    node* r = tempNode->getRightNode();
                    while(r->getLeftNode()!= NULL){
                        r = r->getLeftNode();
                    }
                    r->updateLeftLink(q);

                    delete tempNode;

                }
            }
            return removed;
        }

        // method that returns true if the data is present in the bst
        bool search(int data){
            bool found = false;

            // creating a temp node to traverse the binary tree
            node* tempNode = root;
            while(tempNode != NULL){

                // if data is less than the node element then search on the left hand side
                if(data < tempNode->getElement()){
                    tempNode = tempNode->getLeftNode();
                }
                // if data is greater than the node element search on the right hand side
                else if(data > tempNode->getElement()){
                    tempNode = tempNode->getRightNode();
                }
                // if data is equal to the node element then return true
                else if(data == tempNode->getElement()) {
                    found = true;
                    cout<<"\n\nThe Data "<<data<<" is found in the BST.";
                    return true;
                }
            }
            // if data is not found then return false
            if(not found){
                cout<<"\n\nThe Data "<<data<<" is not found in the BST.";
                return false;
            }
        }

        // method that returns max element of the binary search tree
        // max element appears in the right most node of the bst
        int Max(){
            if(isEmpty()){
                cout<<"The tree is empty!!";
                return -99999;      // assuming -99999 never appeares in the tree
            }
            else{
                // creating a temp node to traverse the tree
                node* tempNode = root;
                // keep traversing to the right node of the bst
                while(tempNode->getRightNode() != NULL){
                    tempNode = tempNode->getRightNode();
                }
                return tempNode->getElement();
            }
        }

        // method that returns min element of the binary search tree
        // max element appears in the left most node of the bst
        int Min(){
            if(isEmpty()){
                cout<<"The tree is empty!!";
                return 99999;       // assuming 99999 never appeares in the tree
            }
            else{
                // creating a temp node to traverse the tree
                node* tempNode = root;
                // keep traversing to the left node of the bst
                while(tempNode->getLeftNode() != NULL){
                    tempNode = tempNode->getLeftNode();
                }
                return tempNode->getElement();
            }
        }

        // recursive program to display tree using Preorder traversal
        void displayPreorder(node* n){

            if(n == NULL){
                return;
            }

            cout<<n->getElement()<<"  ";
            displayPreorder(n->getLeftNode());
            displayPreorder(n->getRightNode());

        }

        // recursive program to display tree using Inorder traversal
        void displayInorder(node* n){

            if(n == NULL){
                return;
            }

            displayInorder(n->getLeftNode());
            cout<<n->getElement()<<"  ";
            displayInorder(n->getRightNode());

        }

        // recursive program to display tree using Postorder traversal
        void displayPostorder(node* n){

            if(n == NULL){
                return;
            }

            displayPostorder(n->getLeftNode());
            displayPostorder(n->getRightNode());
            cout<<n->getElement()<<"  ";
        }

        // method to display all the leaf nodes
        // using inorder traversal to traverse the tree and print all leaf nodes
        void displayLeafNodes(node* n){
            if(n == NULL){
                return;
            }

            displayLeafNodes(n->getLeftNode());

            // leaf node has both left and right links as null
            // checking if both links are null then it is a leaf node
            if(n->getLeftNode() == NULL && n->getRightNode() == NULL){
                cout<<n->getElement()<<"  ";

            }

            displayLeafNodes(n->getRightNode());
        }

        // method to find the common ancestor of 2 data elements
        // both the elements passed to the method must be present in the BST
        void commonAncestor(node* n, int e1, int e2){

            int data = n->getElement();
            static bool printParent = false;
            // if both are greater than the node data then traverse right
            if(data < e1 && data < e2){
                commonAncestor(n->getRightNode(),e1,e2);
            }

            // if both are less than node data then traverse left
            else if(data > e1 && data > e2){
                commonAncestor(n->getLeftNode(),e1,e2);
            }

            // if any element is equal to data then the parent element is the common ancestor
            else if(data == e1 || data == e2){
                printParent = true;
                return;
            }
            // if both above cases are not satisfied then the current node is the common ancestor node
            else{
                cout<<"\n\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
                return;
            }

            if(printParent == true){
                cout<<"\n\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
                // reset static printParent variable
                printParent = false;
            }

        }

        // method to find the height of bst
        // in this method q always marks the root node
        int height(node *p)
        {
            //
            static int pHeight=0,tempHeight=0,x=0;
            // if the node is null then return
            if(p==NULL)
            {
                return 0;
            }
            else
            {

                //else first traverse to the left
                x=height(p->getLeftNode());

                tempHeight++;
                // if we are back at the root node marked by q
                // then check if the depthtree is less that deep
                if(p==this->getRoot())
                {
                    if(pHeight < tempHeight)
                    {
                        pHeight = tempHeight;
                        tempHeight = 0;
                    }
                }
                x=height(p->getRightNode());

            }
            return pHeight+1;
        }

        void printNodeAtDistance(node* p,int distance, int count){

            if(p == NULL){
                return;
            }

            if(count > distance){
                return;
            }
            if(count == distance){
                cout<<p->getElement()<<"  ";
            }
            printNodeAtDistance(p->getLeftNode(),distance,count+1);
            printNodeAtDistance(p->getRightNode(),distance,count+1);
        }

        // method to delete the largest element of the tree
        void deleteMax(){
            int element = this->Max();
            this->deleteElement(element, this->getRoot());
        }

        // method to delete the smallest element of the tree
        void deleteMin(){
            int element = this->Min();
            this->deleteElement(element, this->getRoot());
        }
};

int main()
{
    BST b1;
    b1.insert(7);
    b1.insert(29);
    b1.insert(25);
    b1.insert(36);
    b1.insert(71);
    b1.insert(24);
    b1.insert(5);
    b1.insert(9);
    b1.insert(1);

    node* root = b1.getRoot();
    cout<<"The Root element of the BST is : "<<root->getElement()<<endl;

    cout<<"\nThe Preorder traversal of the BST is : ";
    b1.displayPreorder(root);

    cout<<"\n\nThe Postorder traversal of the BST is : ";
    b1.displayPostorder(root);

    cout<<"\n\nThe Inorder traversal of the BST is : ";
    b1.displayInorder(root);

    cout<<"\n\nThe Leaf nodes of the BST are : ";
    b1.displayLeafNodes(root);

    cout<<"\n\nThe Largest element of the BST is : "<<b1.Max();


    cout<<"\n\nThe Smallest element of the BST is : "<<b1.Min();

    //searching an element in the Linked List
    b1.search(24);
    b1.search(77);

    cout<<"\n\nThe Height of the BST is : "<<b1.height(b1.getRoot());

    b1.commonAncestor(root,24,5);
    b1.commonAncestor(root,1,5);
    b1.commonAncestor(root,25,36);

    cout<<"\n\nThe Elements at a distance of 2 from the root of the BST are : ";
    b1.printNodeAtDistance(root,2,0);

    //deleting leaf element
    b1.deleteElement(1,root);

    //deleting root node
    b1.deleteElement(7,root);

    cout<<"\n";
    root = b1.getRoot();
    b1.displayPreorder(root);

    b1.deleteMin();
    b1.deleteMax();
    cout<<"\n\n";
    b1.displayPreorder(root);
}