Hashmap с использованием неправильной реализации двоичного дерева поиска?

Я практикуюсь в leetcode https://leetcode.com/problems/design-hashmap/description/ пытаюсь реализовать хэш-карту на C++, используя двоичное дерево поиска в качестве базовой структуры данных. Я прохожу большинство тестовых примеров, но есть один очень длинный тест, который говорит о том, что я даю неверный ответ. Однако тестовый пример настолько длинный, что не показывает, что именно в моем ответе неверно, поэтому найти проблему стало очень сложно. Если у кого-то есть опыт работы с двоичными деревьями поиска, что-то не так с моим дизайном? Спасибо за любой совет!

#define MAXBUCKETS 769 // large prime number that to minimize collisions

class Bucket{ //binary search tree bucket for hashmap
    // define what a node looks like
    struct node{
        int key;
        int value;
        struct node *left, *right;
    };
    
    struct node* root;

    
    // create a new node
    struct node* newNode(int newKey, int newValue)
    {
        struct node* temp = new struct node;
        temp->key = newKey;
        temp->value = newValue;
        temp->left = NULL;
        temp->right = NULL;
        return temp;
    }
    
    // insert a new node given its key
    struct node* insertNode(struct node* insertUnder, int newKey, int newVal)
    {
        // tree is empty, create a new node at this point
        // this will make it so that we create roots for empty
        // trees, or add as a leaf in the right location
        if ( insertUnder == NULL)
        {
            return newNode(newKey, newVal);;
        }
        
        // find the right position for this new key and value
        if ( newKey < insertUnder->key)
        {
            // smaller keys to the left
            insertUnder->left = insertNode(insertUnder->left, newKey, newVal);
        }
        else if (newKey > insertUnder->key)
        {
            // bigger keys to the right
            insertUnder->right = insertNode(insertUnder->right, newKey, newVal);
        }
        else
        {
            // matching key, update value
            insertUnder->value = newVal;
        }
        return insertUnder;
    }
    
    // find a node in the tree
    int search(struct node* currentNode, int key)
    {
        if (currentNode == NULL)
        {
            // empty node, so key is not present
            return -1;
        }
        if (currentNode->key == key)
        {
            // found key, return its value
            return currentNode->value;
        }
        if (key < currentNode->key)
        {
            // key could be to the left, search there
            return search(currentNode->left, key);
        }
        else
        {
            // key could be to the right, search there
            return search(currentNode->right, key);
        }
    }
    
        
    // find the predecessor of a node
    struct node* findSuccessor(struct node* node)
    {
        // to find the successor of input node, move to the right
        // to search the nodes bigger than the input node, and 
        // then move to the left as many times as you can to find 
        // the smallest node in that right subree.
        node = node->right;
        while(node->left)
        {
            node = node->left;
        }
        return node;
    }
    
    // find the successor of a node
    struct node* findPredecessor(struct node* node)
    {
        // to find the successor of input node, move to the left
        // to search the nodes smaller than the input node, and 
        // then move to the right as many times as you can to find 
        // the biggest node in that left subree.
        node = node->left;
        while(node->right)
        {
            node = node->right;
        }
        return node;
    }
    
    
    // remove a node from the tree
    struct node* removeNode(struct node* node, int key)
    {
        if (node == NULL)
        {
            // node is empty, done searching
            return NULL;
        }
        
        // search through the tree to find the location of the key
        if (key < node->key)
        {
            node->left = removeNode(node->left, key);
        }
        else if (key > node->key)
        {
            node->right = removeNode(node->right, key);
        }
        
        if (node->key == key)
        {
            // found the right node
            if (node->right == NULL && node->left == NULL) // node is a leaf
            {
                //simply remove the node
                // node = NULL;
                delete node;
                return NULL;
            }
            else
            {
                if (node->right)
                {
                    // node has right child, replace by successor (smallest of right children), 
                    // and delete the successor from the subtree
                    struct node* successor = findSuccessor(node);
                    node->key = successor->key;
                    node->value = successor->value;
                    node->right = removeNode(successor, successor->key);
                    
                }
                else //there is a left child
                {
                    // node has no right child, but has a left child,
                    // so replace by its predecessor (biggest of the left children), and
                    // delete the predecessor from the subtree
                    struct node* predecessor = findPredecessor(node);
                    node->key = predecessor->key;
                    node->value = predecessor->value;
                    node->left = removeNode(predecessor, predecessor->key);
                }
            }
        }
        return node;
    }

    public:
    Bucket(){
        root = NULL;
    }
    void add(int key, int value)
    {
        root = insertNode(root, key, value);
    }
    void remove(int key)
    {
        root = removeNode(root, key);
    }
    int findInBucket(int key)
    {
        return search(root, key);
    }
};

class MyHashMap {
    Bucket buckets[MAXBUCKETS];
public:
    MyHashMap() {
        for(int i = 0; i < MAXBUCKETS; i++)
        {
            buckets[i] = Bucket();
        }
    }
    
    void put(int key, int value) {
        int bucketi = key % MAXBUCKETS;
        buckets[bucketi].add(key, value);
    }
    
    int get(int key) {
        int bucketi = key % MAXBUCKETS;
        return buckets[bucketi].findInBucket(key);
    }
    
    void remove(int key) {
        int bucketi = key % MAXBUCKETS;
        buckets[bucketi].remove(key);
    }
};



/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */