-1
void insert(int key)
{
    insertRec(key, root);
}

void insertRec(int key, Node *current)
{
    if(current==NULL)
        current = new Node(key);
    else if(key <= current->value)
        insertRec(key, current->leftChild);
    else
        insertRec(key, current->rightChild);
}

How come this doesn't work?

In the insert function, key value and root of the tree are passed to insertRec. If the node is null, create a new node and set it to the key value. Else, either recursively go left or right until the node hits a null spot and insert a new node there.

Zong
  • 6,160
  • 5
  • 32
  • 46
Raymond
  • 11
  • 1
  • 1
    [Find a good beginners book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) and read about passing arguments *by reference*. – Some programmer dude Apr 21 '16 at 05:05
  • 3
    Assigning a local variable `current` isn't the same as inserting the node. It just modifies the local variable, not *what the variable is referring to*, which is what you want. For future reference, try to avoid just saying stuff "doesn't work". Describe *how* your code doesn't work. – Zong Apr 21 '16 at 05:07
  • `void insertRec(int key, Node *&current)` should do the trick. – πάντα ῥεῖ Apr 21 '16 at 05:22

1 Answers1

2

It's not true the code 'doesn't work'. Of course it works, just as it is written. The problem is you wrote something different from what you need.

when you pass an argument to insertRec(), the routine gets a copy of a pointer to the Node object. So when you assign a value in

    current = new Node(key);

you overwrite a local copy in the local variable current. The calling function (and its data) do not know about it.

If you want the caller to recieve the new value, declare a function takes a reference to a variable:

void insertRec(int key, Node *&current)
CiaPan
  • 9,381
  • 2
  • 21
  • 35
  • Thank you. Adding a & made the code work as I intended. But I'm confused about * and &. I thought they both point to the same address, in this case it's the address of the root node, and I can modify the value through the pointer current. – Raymond Apr 21 '16 at 05:43
  • This is no way strange, just a reference to a pointer. Such reference is just a pointer under a mask. You can make it an explicit pointer to a pointer by declaring `void insertRec(int key, Node **current)` and calling it with `insertRec(key, &(current->leftChild));` (inner parenthese not necessary, added just for readability). Then the main assignment should look like `*current = new Node(key);` with an explicit dereference. – CiaPan Apr 21 '16 at 05:53