Implementing a binary tree in C++ using "std::unique_ptr"

Question

I have implemented a simple binary search tree class in C++ using std::unique_ptr objects to hold the pointers to each node. In doing this I have come across a situation that is somewhat questionable in the Delete method. Since I can't copy the unique pointers, but I need a way to traverse the tree with a "temporary" pointer, I had to resort to using a raw pointer to do the traversal.

This is the section I am talking about (In the Delete method):

// Need to use a raw pointer because I can't assign to a std::unique_ptr
Node* n = node.get();
while (n->right) {

  // Using a reference to a unique_ptr instead of a raw pointer will cause this line to fail to compile
  n = n->right.get();
}

Is this an acceptable thing to do?

It compiles and runs. And since the underlying pointer is still managed by a unique_ptr object it will be deleted properly. Everything about this works fine, but it just doesn't feel right for some reason.

The full source code is shown below (Feel free to comment on anything else that may be improved as well):

#include <iostream>
#include <memory>

using std::make_unique;
using std::unique_ptr;

template <typename T>
class Tree {

  struct Node {
    Node(const T& value)
      : value(value), left(nullptr), right(nullptr) {}

    T value;
    unique_ptr<Node> left;
    unique_ptr<Node> right;
  };

public:
  Tree() : root_(nullptr) {}

  // Insert a value into the tree
  void Insert(const T& value) {
    Insert(root_, value);
  }

  // Delete a value from the tree
  bool Delete(const T& value) {
    return Delete(root_, value);
  }

  // Search the tree for a node and return true if it is found
  bool Contains(const T& value) const {
    return Contains(root_, value);
  }

private:
  void Insert(unique_ptr<Node>& node, const T& value) {
    if (not node) {
      node = make_unique<Node>(value);
    }
    else {
      value < node->value
        ? Insert(node->left, value)
        : Insert(node->right, value);
    }
  }

  bool Delete(unique_ptr<Node>& node, const T& value) {
    if (not node) {
      return false;
    }
    else if (value == node->value) {
      if (node->left) {
        unique_ptr<Node>& right = node->right;
        node = move(node->left);
        if (right) {

          // Need to use a raw pointer because I can't assign to a std::unique_ptr
          Node* n = node.get();
          while (n->right) {

            // Using a reference to a unique_ptr instead of a raw pointer will cause this line to fail to compile
            n = n->right.get();
          }
          n->right = move(right);
        }
      }
      else {
        node = move(node->right);
      }
      return true;
    }
    else {
      return value < node->value
        ? Delete(node->left, value)
        : Delete(node->right, value);
    }
  }

  bool Contains(const unique_ptr<Node>& node, const T& value) const {
    if (not node) {
      return false;
    }
    else if (node->value == value) {
      return true;
    }
    else {
      return value < node->value
        ? Contains(node->left, value)
        : Contains(node->right, value);
    }
  }

  unique_ptr<Node> root_;
};

Answer 1

On raw and smart pointers

First, I'll address your specific question, about using a raw pointer to refer to nodes in the tree. I believe you're doing exactly the right thing here, because smart pointers convey information about ownership of the resource.

We are looking at nodes that are owned by the tree (actually, each node is owned by its parent), and it's entirely appropriate that that ownership is encoded as a std::unique_ptr; that says that this is the only place that's responsible for deleting the node when it's no longer required.

Our Delete method walks nodes from the root downwards; it needs to refer to the nodes, but only during the execution of the method (it doesn't store pointers anywhere). A raw pointer is perfectly suitable here.

---

General review

Is <iostream> used anywhere? I think it can be omitted.

If this is a header file, avoid bringing std::make_unique and std::unique_ptr into the global namespace, as that will affect every file that includes the header. It's reasonable to do so inside the function bodies, but at that point it's likely better to simply use the qualified names. Including them within the scope of the type is a middle ground where opinions will differ.

We should include <utility> for std::move (and the same comments apply to importing that name into ::).

Consider turning tests around to test a positive first, which slightly reduces cognitive load. Instead of:

if (not node) {
  node = make_unique<Node>(value);
}
else {
  value < node->value
    ? Insert(node->left, value)
    : Insert(node->right, value);
}

This is easier to reason about:

if (node) {
  value < node->value
    ? Insert(node->left, value)
    : Insert(node->right, value);
}
else {
  node = make_unique<Node>(value);
}

Actually, that ternary can be narrowed to within the argument list (you can add more parens according to taste):

if (node) {
  Insert(value < node->value ? node->left : node->right, value);
}
else {
  node = make_unique<Node>(value);
}

On a related note, if we return early from within if, we can just flow into the next code without else:

if (not node) {
  return false;
}
else if (node->value == value) {
  return true;
}
else {
  return value < node->value
    ? Contains(node->left, value)
    : Contains(node->right, value);
}

That can become

if (not node) {
  return false;
}
if (node->value == value) {
  return true;
}

return Contains(value < node->value ? node->left : node->right, value);

We might be able to remove some repetition by adding a method to find the insertion point for a value - Contains() can return true if that insertion point has a value that compares equal, and Delete() can start from that point in removing the value.

If the tree could be large, then perhaps iteration may be better than recursion for walking the tree. That means we'll need pointers in some places where we currently have references, and some things may have to lose const qualification, but may give a performance improvement and save on stack usage (or may not, depending on how your compiler manages to optimise the recursive call - always check these things!).

---

Further directions

Try to evolve the public interface to supporting standard container operations. This probably begins with creating iterators and the member functions that return them.

Consider maintaining a balanced tree - you'll want to read up on the theory if you're not already familiar with the techniques to do this.

You haven't shown your unit tests here, but it's worthwhile occasionally running them with a memory checker such as Valgrind. As well as ensuring we don't leak memory, that will also help identify any uses of dangling pointers or uninitialized values, which an ordinary run might not.

Answer 2

Here are some ideas to help you improve your program.

Fix the bug

If we create a Tree<std::string> t and then insert "epsilon", "gamma", "beta", "delta", "alpha", "mu", and "kappa" in that order, we have a tree like this:

If we then call t.Delete("beta"); we invoke undefined behavior and mess up the tree by effectively deleting two nodes (both "beta" and "delta" are now gone):

Use raw pointers

The usual advice is to replace raw pointers with smart pointers, but in this particular case, I would advise going the other way for a number of reasons. First, the std::unique_ptr is not part of the public interface of the tree, so changing it to a raw pointer would not affect users of the tree at all. Second, the smart pointer is only getting in the way here, since it would be much simpler to write this code with plain pointers. Third, a plain pointer version would better allow you to have a single private concrete implementation class using a void * for the data. The template would then only have a very light wrapper to convert to and from void * to type T. This makes it certain that if you have multiple kinds of trees, there will only be one code instance that actually implements the tree manipulations and each templated version will only have a small bit of code overhead per type.

Avoid polluting the global namespace with using

The using std::make_unique and using std::unique_ptr in this code are at file scope. If this is intended to be an include file, then that effectively brings those to into the global scope which could cause name collisions. Instead, you could simply remove those and simply add std:: where appropriate or omit them entirely if you follow the previous suggestion.

Don't define a constructor that only initializes data

The only thing your Tree constructor does is to initialize root_ to a fixed value. It's generally better to instead use member initializers instead. See Cpp Guidelines C.45. I'd also simplify the Node constructor by using member initializers for left and right.

Provide a usable interface

The way it's currently defined, it's not possible to do anything at all with nodes once they are stored in the Tree except to determine whether they're stored in the tree. That's unlikely to be a useful interface in the real world.

Use only necessary #includes

The #include <iostream> line is not necessary and can be safely removed.

Consider using more idiomatic C++

While your use of not is not technically wrong, you should be aware that many experienced C++ programmers will be unfamiliar with alternative operators, and so if others read your code, it might be an impediment to their understanding of it.

Answer 3

unique_ptr<Node>& right = node->right;
node = move(node->left); // it will destroy the previous node and right nodes
if (right) // right will be nullptr as the right nodes would have been destructed in the previous line
{...}

In your Delete() function, this logic seems to be flawed. When you move your node->left into node, then all the existing right nodes will be destroyed because you just created a reference of unique_ptr which doesn't stop the following move operation from deleting these nodes.

if (right) {...}

So, in effect the above condition will never be true and also, you will lose the right nodes.

The correct way to do this will be to move the right nodes into a local variable something like this :

auto right = std::move(node->right);
node = move(node->left);
if (right)  // Now, right will contain all the right nodes
{...}