I'm doing some leetcode practice https://leetcode.com/problems/design-hashmap/description/ trying to implement a hashmap in C++ using a binary search tree as the underlying data structure. I'm passing most of the test cases but there is one really long test case which says I'm giving an incorrect answer. However, the test case is so long that it doesn't show me what about my answer is wrong, so it has become very hard to find the problem. For someone with experience with binary search trees, is there something wrong with my design? Thank you for any advice!
#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);
*/
The line
node->right = removeNode(successor, successor->key);
is incorrect, as the successor may not be exactly the right child of node, in which case a portion of the tree will be lost.
Fortunately, the fix is simple:
node->right = removeNode(node->right, successor->key);
The same issue needs to fixed in the other branch, when replacing the node with the in-order predecessor.
node->left = removeNode(node->left, predecessor->key);