Member pointer being overwritten on function return?

Question

I've been practicing my C++, as it's gotten a little rusty since college, and I'm having a bizarre problem where a member value is being overwritten as soon as my function returns.

template <class T>
class BstNode
{
    public:
        T value;
        BstNode<T>* left;
        BstNode<T>* right;
        BstNode<T>* parent;

        BstNode()
        { left = right = parent = NULL; }
        BstNode(T value)
        { this->value=value; left=right=parent=NULL;}
        BstNode(T value, BstNode<T>* parent)
        { this->value=value; this->parent=parent; left=right=NULL;}
};

template <class T>
class BinarySearchTree 
{
    protected:
        BstNode<T>* root;

        void removeNode(BstNode<T>* node);
        void addChild(T value, BstNode<T>* node);
        BstNode<T>* find(T value, BstNode<T>* node);
    public:
        BinarySearchTree()
        { root = NULL; }
        ~BinarySearchTree()
        { removeNode(root); }

        BinarySearchTree<T> insert(T value);
        bool contains(T value);
        BinarySearchTree<T> remove(T value);

        void print();

        BstNode<T>* getRoot() {return root;}

};

template <class T>
BinarySearchTree<T> BinarySearchTree<T>::insert(T value)
{
    if (root == NULL)
    {
        root = new BstNode<T>(value);       
    }
    else
    {
        addChild(value, root);
    }
    cout << "VAL: " << root->value << endl << "LEFT: " << root->left << endl << "RIGHT: "<< root->right << endl << "ADDR: " << root <<endl;
    return *this;
}
template <class T>
void BinarySearchTree<T>::addChild(T value, BstNode<T>* node)
{

    if (value > node->value)
    {
        cout <<"\tgt"<<endl;
        if (node->right == NULL)
        {
            node->right = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->right);
        }
    }
    else
    {
        cout<<"\tlte"<<endl;
        if (node->left == NULL)
        {
            node->left = new BstNode<T>(value, node);
        }
        else
        {
            addChild(value, node->left);
        }
    }
}

// [other member functions]


int main()
{
    BinarySearchTree<int> tree;
    BstNode<int> *n;
    n = tree.getRoot();
    cout << "ADDR: " << n <<endl<<endl;
    tree.insert(5);
    n = tree.getRoot();

    cout << "VAL: " << n->value << endl << "LEFT: " << n->left << endl << "RIGHT: "<< n->right << endl << "ADDR: " << n << endl;
    return 1;
}

The output of my function is:

$ ./bst
ADDR: 0

VAL: 5
LEFT: 0
RIGHT: 0
ADDR: 0xa917c8

VAL: 11085080
LEFT: 0xa917a8
RIGHT: 0
ADDR: 0xa917c8

I don't understand why the values in the root node changed, but the pointer is still pointing at the same location. The only thing I could think of is that the root node is being created on the stack instead being allocated in the heap, but doesn't new make sure that memory is allocated correctly in C++?

Answer 1

I think the issue is that your insert method returns the BinarySearchTree by value, but you don't have a copy constructor defined. As a result, this makes a shallow copy of the BinarySearchTree, returns it, and causes the copy's destructor to fire. This then deletes the BstNode stored as the root, but since the copied BinarySearchTree shares BstNodes with the original tree, you're trashing memory in the original tree. The error you're getting is from accessing deallocated memory when you try to access the node again.

To fix this, either have the insert function return a reference to the tree (so no copy is made) or define a copy constructor or assignment operator. Ideally, do both. :-)

Hope this helps!