BST with duplicate value.cpp

struct Node{
    int key;
    int count;
    Node *left, *right;
};

class BST{
private:
    Node *root;

    Node* getNewNode(int x){
        Node* t = new Node;
        t->key = x;
        t->count = 1;
        t->left = t->right = NULL;
        return t;
    }
    Node* makeEmpty(Node* t){
        if(t == NULL) return NULL;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
        return NULL;
    }
    Node* insert(Node* t, int x){
        if(t == NULL){
            return getNewNode(x);
        }
        if(x == t->key){
            (t->count)++;
            return t;
        }
        if(x < t->key){
            t->left = insert(t->left, x);
        }
        else if(x > t->key){
            t->right = insert(t->right, x);
        }
        return t;
    }
    Node* findMin(Node* t){
        if(t == NULL){
            return NULL;
        }
        else if(t->left == NULL){
            return t;
        }
        else{
            return findMin(t->left);
        }
    }
    Node* findMax(Node* t){
        if(t == NULL){
            return NULL;
        }
        else if(t->right == NULL){
            return t;
        }
        else{
            return findMax(t->right);
        }
    }
    Node* remove(Node *t, int x){
        if(t == NULL) return NULL;
        if(x < t->key){
            t->left = remove(t->left, x);
        }
        else if(x > t->key){
            t->right = remove(t->right, x);
        }
        else{
            if(t->count > 1){
                (t->count)--;
                return t;
            }

            if(t->left == NULL){
                Node* temp = t->right;
                delete t;
                return temp;
            }
            else if(t->right == NULL){
                Node* temp = t->left;
                delete t;
                return temp;
            }

            Node* temp = findMin(t->right);

            t->key = temp->key;
            t->count = temp->count;

            t->right = remove(t->right, temp->key);
        }
        return t;
    }
    bool find(Node* t, int x){
        if(t == NULL) return false;
        if(t->key == x) return true;
        else if(x < t->key){
            return find(t->left, x);
        }
        else if(x > t->key){
            return find(t->right, x);
        }
    }
    void inorder(Node* t) {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->key << " ";
        inorder(t->right);
    }
public:
    BST(){
        root = NULL;
    }
    ~BST(){
        root = makeEmpty(root);
    }
    void insert(int x){
        root = insert(root, x);
    }
    void remove(int x){
        root = remove(root, x);
    }
    void display(){
        inorder(root);
        cout << endl;
    }
};