# Recursive binary search tree - follow-up

This is a follow-up to

Recursive binary search tree

changes:

• Used raw pointers rather than std::unique_ptr
• const correctness
• Made variable names more beautiful
• implemented at()

How can I improve this code?

template<typename K, typename V>
class binarySearchTree {

struct Node {
K key;
V val;
Node* left;
Node* right;
Node(const K& k, const V& v) : key(k), val(v), left(nullptr), right(nullptr) { }
};

void check(Node* node) {
if (node == nullptr) {
throw std::runtime_error("No node");
}
}

V& at(Node* node, const K& key) {
if (node == nullptr) {
throw std::runtime_error("no node");
}
if (key < node->key) {
return at(node->left,key);
} else if (key > node->key) {
return at(node->right,key);
}
return node->val;
}

V& get(Node*& node, const K& key) {
if (node == nullptr) {
node = new Node{key,{}};
++n;
return node->val;
}
if (key < node->key) {
return get(node->left,key);
} else if (key > node->key) {
return get(node->right,key);
} else {
return node->val;
}
}

Node* min(Node* node) const {
if (node->left == nullptr) {
return node;
}
return min(node->left);
}

Node* max(Node* node) const {
if (node->right == nullptr) {
return node;
}
return max(node->right);
}

Node* remove_min(Node*& node) {
if (node->left == nullptr) {
Node* x = node->right;
delete node;
--n;
return x;
}
node->left = remove_min(node->left);
return node;
}

Node* remove_max(Node*& node) {
if (node->right == nullptr) {
Node* x = node->left;
delete node;
--n;
return x;
}
node->right = remove_max(node->right);
return node;
}

Node* remove(Node*& node, K key) {
check(node);
if      (key < node->key){
node->left = remove(node->left,  key);
} else if (key > node->key){
node->right = remove(node->right, key);
} else {
if (node->right == nullptr) {
Node* x =  node->left;
delete node;
--n;
return x;
}
if (node->left == nullptr) {
Node* x = node->right;
delete node;
--n;
return x;
}
Node* old = node;
node = min(old->right);
node->right = remove_min(old->right);
node->left = old->left;
delete old;
--n;
}
return node;
}

void traverse(Node* node) {
if (node == nullptr) {
return;
}
traverse(node->left);
std::cout << node->key << " " << node->val << '\n';
traverse(node->right);
}

void destruct(Node* node) {
if (node == nullptr) {
return;
}
destruct(node->left);
destruct(node->right);
delete node;
}

Node* root;
std::size_t n;

public:

binarySearchTree() :root{nullptr},n{0} { }
//no compy/move

std::size_t size() const {
return n;
}

V& at(const K& key) {
return at(root,key);
}

V& operator[](const K& key) {
return get(root,key);
}

K& min() {
check(root);
return min(root)->key;;
}

K& max() {
check(root);
return max(root)->key;
}

void remove_min() {
check(root);
root = remove_min(root);
}

void remove_max() {
check(root);
root = remove_max(root);
}

void remove(K key) {
root = remove(root, key);
}

void traverse() {
traverse(root);
}

~binarySearchTree() {
destruct(root);
}

};

• If there is no copy/move. Then you should explicitly delete them otherwise the compiler will generate them for you. Currently you are failing the rule of 5. Jan 12 '15 at 18:15

V& at(Node* node, const K& key)
V& get(Node*& node, const K& key)
Node* min(Node* node) const
Node* max(Node* node) const
Node* remove_min(Node*& node)
Node* remove_max(Node*& node)
Node* remove(Node*& node, K key)
void traverse(Node* node)


can and should easily be reworked into members of Node. Try it and see how much less typing of node-> it will result in.

This method:

void destruct(Node* node)


should really just be the destructor ~Node(), and in ~binarySearchTree() simply call delete root. Calling delete on a null pointer is perfectly fine so you don't even need to check for null here.

So you only really need this:

    ~Node() {
delete left;
delete right;
}

~binarySearchTree(){
delete root;
}


to clean up after you. Please note that if you do this, you need to completely detach a node from the tree in your remove* methods before deleting it, otherwise the children will go too. But I find this to be better style anyway; detach, re-link tree, then delete.

Also you're being inconsistent with your naming, you have Node and binarySearchTree. Either Node should be node (first letter of first word is lower case), or binarySearchTree should be BinarySearchTree (first letter of all words is upper case). Personally, I prefer the later.

You make a check(Node*) function and then you don't use it in the first method following it; probably an oversight.

You should make const versions of your operator[] and at besides the non-const versions (the idea is that all non-mutating operations should be doable with a const tree):

V& at(const K& key) {
return at(root,key);
}

const V& at(const K& key) const {
return at(root,key);//also make a const at
}

V& operator[](const K& key) {
return get(root,key);
}

const V& operator[](const K& key) const {
return get(root,key);//also make a const get
}


min and max should be const and return a const reference (allowing users to change the key like that would invalidate the structure of the tree).

const K& min() const {
check(root);
return min(root)->key;
}

const K& max() const {
check(root);
return max(root)->key;
}


Why not make traverse() take a functor that accepts key/value so that you can do stuff on your traversal?

void traverse(std::function<void(K,V)>& f) {traverse(f, root);}
void traverse(std::function<void(K,V)>& f, Node* node) {
if (node == nullptr) {
return;
}
traverse(f, node->left);
f(node->key, node->val);
traverse(f, node->right);
}


Then printing is simply:

tree.traverse([](K const& k, V const& v){std::cout << k << " " << v << '\n';});


But it can also do other interesting things if need be.

There are a lot of inconsistency in your code and a few cases where you follow an if-block with something that probably should be in an else if- or else-block.

There are also functions that have return-values that really have nothing to do there.
I'll try to illustrate with the one function I found an actual error in.
The rewrite is as follows.

void remove(Node*& node, const K& key) {
check(node);
if (key < node->key) {
remove(node->left, key);
} else if (key > node->key) {
remove(node->right, key);
} else {
Node* old = node;
if (node->right == nullptr) {
node = node->left;
} else if (node->left == nullptr) {
node = node->right;
} else {
node = min(old->right);
// remove_min actually removes the node you just replaced above.
node->right = // remove_min(old->right);
node->left = old->left;
}
delete old;
--n;
}
}


As mentioned above, this function actually removes both the node you want to remove and the node you try to replace it with in the last case.

Fixing that error is something I leave as an exercise.

• "Fixing that error is something I leave as an exercise." - as you mentioned, I shouldn't use remove_min(old->right); because it will actually delete the node that I will use to replace the deleted node. I never noticed this because this code originally used unique_ptr. To fix, I changed node->right to point to the second smallest key in the right subtree of the deleted node, like this: node->right = old->right->right;. I think it's working correctly. What do you think? Jan 14 '15 at 13:46
• That would cut away everything above the node you are moving. The problem is that remove_min actually deletes the node you want to keep. You just want it removed from it's current location in the tree. Jan 14 '15 at 14:54
• "That would cut away everything above the node you are moving." - I don't understand what you mean here. In my code in the comment above, I reset node to point to old->right to replace the deleted node. Then I reset node->right to point to the right subtree of node->right. Can you explain further? Jan 14 '15 at 15:32
• After replacing the old node with min(old->right), you still need all other nodes in old->right. All the nodes in old->right->left are missing if you do it that way. You have to actually graft min(old->right)->right all the way down where min(old->right) was. remove_min as a function would work perfectly except for the fact that it deletes the node it is just supposed to remove. Jan 14 '15 at 17:17
• I created a new Node and stored the node returned by remove_min(old->right)'s data to it, like this: node = new Node{min(old->right)->key, min(old->right)->val};. So it doesn't matter when node->right = remove_min(old->right); deletes. What do you think? Jan 15 '15 at 15:46