C++: where are my new nodes?

Question

I am trying to add element in a Set using Binary Tree:

bool TreeSet::add(const string &str)
{
    if (treesize == 0)
    {
        TreeNode->data = str;
        treesize++;
        return true;
    }
    else
    {
        if (str < TreeNode->data)
            return insert(TreeNode->left, str);
        else if (str > TreeNode->data)
            return insert(TreeNode->right, str);
        else
            return false;
    }
    return false;
}

bool TreeSet::insert(TREE *node, const string &str) //private
{
    if (node == NULL)
    {
        node = new TREE;
        node->data=str;
        node->left = NULL;
        node->right = NULL;
        treesize++;
        return true;
    }
    else
    {
        if (str < node->data)
            return insert(node->left, str);
        else if (str > node->data)
            return insert(node->right, str);
        else
            return false;
    }
    return false;
}

As you can see, I want to initialize a TREE struct inside of insert and when I finish doing this I want to link it with the left or right node of the tree.

But when I gdb this, only 1 level of tree (top level) can be constructed, the *left and *right node are NULL no matter how many strings I was trying to add to it. Why?

My TREE is:

typedef struct tree
{
    string data;
    tree *left;
    tree *right;
} TREE;

Probably you have some [rule of three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) problems. — πάντα ῥεῖ, Oct 02 '14 at 17:17

AndyG · Accepted Answer · 2014-10-02T17:23:41.020

bool TreeSet::insert(TREE *node

should be

bool TreeSet::insert(TREE *&node

Pointers can also be passed by reference, and should be if you intend to modify them directly. Otherwise you pass by copy and you now have two pointers pointing at the same location. When you use the copied one to new up some data, it now points to a new memory location, leaving your original pointer still as NULL (nullptr in C++11)

On a side note, when a tree gets constructed, you should probably initialize left and right to NULL (nullptr in C++11):

typedef struct tree
{
    string data;
    tree *left;
    tree *right;
    tree():left(NULL),right(NULL){}
} TREE;

Thanks. I have its class constructor initialize to NULL. – hlx98007 Oct 02 '14 at 17:28 — hlx98007, Oct 02 '14 at 17:28

Felix Glas · Answer 2 · 2014-10-02T17:33:05.347

When you pass a pointer as a parameter in the function insert like this:

bool TreeSet::insert(TREE* node, const string& str);

then the pointer is copied into the argument node. Pointing node to something else only points the local copy of the pointer. The pointer passed to the function from the call site is unchanged.

node = new TREE; // Points local variable 'node' to newly allocated data.
                 // When the function goes out of scope 'node' will be destroyed
                 // and the memory will be leaked.

To change where the original call site pointer points, take the parameter by reference (or add another level of indirection):

bool TreeSet::insert(TREE*& node, const string& str);

By taking a parameter by reference, you make sure you are accessing the call site variable and not a local copy.

C++: where are my new nodes?

2 Answers2