Using smart pointers for C++ binary search tree

Question

I have implemented a binary search tree in c++. Instead of using bare pointers to point to a nodes children I used the std::shared_ptr. The nodes of the tree are implemented as follows

struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;

struct treeNode {
    T key;
    pTreeNode left;
    pTreeNode right;
    treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};

When removing a node from the BST, one of the cases is when the node has only one child. The node is simply replaced by this child as shown below:

             |        remove node                  
            node      --------->     |
               \                    right 
              right                

In an similar Java implementation this can be coded as:

node = node.getRight();

In my C++ implementation it is:

node = node->right;

where node is of type pTreeNode.

When calling the = operator on an pTreeNode (std::shared_ptr<TreeNode>), node's destructor will be called. The number of shared pointers pointing to the underlying TreeNode is 1, hence the TreeNode is destroyed freeing its memory. When the TreeNode (default) destructor is called, each of its members are destroyed. This surely would result in the pTreeNode right member being destroyed. The problem is that node->right is what is being assigned to node. When testing my BST, it appears to work fine with no errors/memory leaks.

• Is what I am doing unsafe?
• If it is unsafe, what could I do to get around this problem?

A 'hack' that i figured may work would be to make another pointer to increase its reference count. Would this be an adequate solution?

//increase reference to node->right by 1 so it doesn't get destroyed
pTreeNode temp(node->right);
node = node->right;

Answer 1

You are apparently assuming that, in

node = right;

shared_ptr's assignment operator may decrement node's count before having finished reading from right (or before incrementing the ref count used by right). However, according to cppreference, using

template<typename T>
template<typename U>
std::shared_ptr<T> &std::shared_ptr<T>::operator =(const std::shared_ptr<U> &);

as

node = right; // std::shared_ptr<treeNode>

is equivalent to

std::shared_ptr<treeNode>(right).swap(node);

which is safe because right is copied before the old value of node is destroyed. As an aside, I have implemented a shared pointer myself and I saw to it that "cleaning up" the old value is the last thing I do inside of operator = precisely to avoid such problems.