Implementing a binary tree in C++ using "std::unique_ptr" 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-&gt;right) {

  // Using a reference to a unique_ptr instead of a raw pointer will cause this line to fail to compile
  n = n-&gt;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 &lt;iostream&gt;
#include &lt;memory&gt;

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

template &lt;typename T&gt;
class Tree {

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

    T value;
    unique_ptr&lt;Node&gt; left;
    unique_ptr&lt;Node&gt; right;
  };

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

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

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

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

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

  bool Delete(unique_ptr&lt;Node&gt;&amp; node, const T&amp; value) {
    if (not node) {
      return false;
    }
    else if (value == node-&gt;value) {
      if (node-&gt;left) {
        unique_ptr&lt;Node&gt;&amp; right = node-&gt;right;
        node = move(node-&gt;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-&gt;right) {

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

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

  unique_ptr&lt;Node&gt; root_;
};
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 &lt;iostream&gt; 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 reasonably 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 &lt;utility&gt; 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&lt;Node&gt;(value);
}
else {
  value &lt; node-&gt;value
    ? Insert(node-&gt;left, value)
    : Insert(node-&gt;right, value);
}



This is easier to reason about:

if (node) {
  value &lt; node-&gt;value
    ? Insert(node-&gt;left, value)
    : Insert(node-&gt;right, value);
}
else {
  node = make_unique&lt;Node&gt;(value);
}


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

if (node) {
  Insert(value &lt; node-&gt;value ? node-&gt;left : node-&gt;right, value);
}
else {
  node = make_unique&lt;Node&gt;(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-&gt;value == value) {
  return true;
}
else {
  return value &lt; node-&gt;value
    ? Contains(node-&gt;left, value)
    : Contains(node-&gt;right, value);
}



That can become

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

return Contains(value &lt; node-&gt;value ? node-&gt;left : node-&gt;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.