Binary Search Tree implementation using smart pointers

Question

I have implemented below code for binary search tree implementation using shared pointer. At present, I have considered only integers. It supports insertion and deletion of values. Also, a print method is implemented for inorder traversal.

Please review and provide your suggestions.

class Bst {
 struct node {
 int val;
 shared_ptr<node> left, right;
 node(int v) : val(v), left(nullptr), right(nullptr){} 
 };
 shared_ptr<node> root;
 shared_ptr<node> _insert(shared_ptr<node> curr, int val);
 shared_ptr<node> _del(shared_ptr<node> curr, int val);
 shared_ptr<node> findmin(shared_ptr<node> curr);
 void _print(shared_ptr<node> curr);
public:
 void insert(int val) { root = _insert(root, val); }
 void del(int val) { root = _del(root, val); }
 void print() { _print(root); cout << '\n'; }
};
shared_ptr<Bst::node> Bst::_insert(shared_ptr<node> curr, int val)
{
 if (curr == nullptr)
 return make_shared<node>(val);
 if (val < curr->val)
 curr->left = _insert(curr->left, val);
 else
 curr->right = _insert(curr->right, val);
 return curr;
}
shared_ptr<Bst::node> Bst::findmin(shared_ptr<node> curr)
{
 while (curr->left)
 curr = curr->left;
 return curr;
}
shared_ptr<Bst::node> Bst::_del(shared_ptr<node> curr, int val)
{
 if (val < curr->val)
 curr->left = _del(curr->left, val);
 else if (val > curr->val)
 curr->right = _del(curr->right, val);
 else {
 if (curr->right == nullptr)
 return curr->left;
 if (curr->left == nullptr)
 return curr->right;
 shared_ptr<node> temp = findmin(curr->right);
 curr->val = temp->val;
 curr->right = _del(curr->right, curr->val);
 }
 return curr;
}
void Bst::_print(shared_ptr<node> curr)
{
 if (curr == nullptr)
 return;
 _print(curr->left);
 cout << curr->val << " ";
 _print(curr->right);
}

Answer 1

• please do not using namespace std;
• why has Bst::findmin no prefix _?
• why do you use std::shared_ptr<> at all? std::shared_ptr is ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes. std::unique_ptr<> is a better candidate.
• it is generally good to separate the data structure from its serialization. Make print a separate function and also handle the member printing outside of the class.

---

Edit As you had trouble getting the unique_ptr running, here's what works for me.

Modify the node to use unique_ptr:

struct node
{
 int val;
 std::unique_ptr<node> left;
 std::unique_ptr<node> right;
 // c'tor left out
};

Also, use a unique_ptr for root. You'll receive heavy compiler complaints, because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:

void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);

Sample implementation for _insert:

void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
 if (!curr)
 {
 curr = std::make_unique<node>(val);
 return;
 }
 if (val < curr->val)
 {
 _insert(curr->left, val);
 }
 else
 {
 _insert(curr->right, val);
 }
}

Your public insert method would be something like:

void insert(int val)
{ 
 _insert(root, val);
}

Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.

---

Edit 2 Separate output from data storage:

A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.

class Bst
{
...
 // traverse with function pointer
 void traverse(void (*func)(int));
};
int main()
{
 Bst b;
 // insert data ... 
 b.traverse([](auto v){ std::cout << v << " "; });
 std::cout << "\n";
}

• bornfree: I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
• Cornholio: You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers as cin or shared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
• bornfree: Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?

Answer 2

• Separate your class declaration and definition into separate Bst.h and Bst.cpp files
• For Bst.h provide header guards
• initialize shared_ptr<node> member, root with nullptr

• bornfree: I thought root will be initialized to nullptr by default ?

Answer 3

You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.

More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.

So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.

(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)

If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).