BinaryTree Insertion

Question

So I already have this Insert function for a Value in my Tree how can I convert it to this type of void function?

void InsertValue(Node* root, int value){

this is my normal function:

Node* Insert(Node* root,int value) {
    if(root == NULL) { // empty tree
        root = CreateNode(value);
    }
    // if data to be inserted is lesser, insert in left subtree.
    else if(value <= root->value) {
        root->left = Insert(root->left,value);
    }
    // else, insert in right subtree.
    else {
        root->right = Insert(root->right,value);
    }
    return root;
}

Thanks for your help

There is no need to return anything from this function as it is already passed to the function as pointer argument. So what ever you are changing will reflect to the calling part. — Sridhar DD, Dec 15 '14 at 14:31
Please show more code; why do you need a different function? — Codor, Dec 15 '14 at 14:34
@SridharDD that is flat out wrong. Consider what happens when `root == nullptr`: you then need to return something since the pointer `root` is passed into the function by value. — Nik Bougalis, Dec 15 '14 at 14:36

score 2 · Answer 1 · answered Dec 15 '14 at 14:49

2

You can do one of two things:

Make root a pointer to a pointer. This can work well but the syntax can be a bit awkward, requiring you to dereference root prior to use.
Use a reference to a pointer. A reference gives you the "power" of the double pointer mentioned above without any of the awkward syntax and it's trivial to do.

So option #2 it is. How to do it? Simply change he function to accept root as a reference to a pointer.

void InsertNode(Node*& root, int value)
{
    // your existing code!
}

answered Dec 15 '14 at 14:49

Nik Bougalis

10,382
1
20
37

Ahh thank you Sir but I still have the problem that my function returns a pointer to a pointer if I call `root->left` which is different to Node*&. – Franklinprogs Dec 15 '14 at 15:01
Ok I get the difference but my function does not accept returning something if it is of type void so just inserting my function does not really work. – Franklinprogs Dec 15 '14 at 15:11
Of course: if you make your function return `void` you can't return anything from it. You need to adjust the way you call the function recursively. The modification should be very obvious. – Nik Bougalis Dec 15 '14 at 18:00
Do you mean an incremental way? `else if(value <= root->value) {` `root->left = CreateNode(value);` `CreateNode(value)->left++;}` could this work? – Franklinprogs Dec 15 '14 at 18:18
I'd suggest you look at @WhozCraig's excellent answer which goes into more detail about this and includes code. Good luck. – Nik Bougalis Dec 15 '14 at 19:49

score 1 · Answer 2 · answered Dec 15 '14 at 18:53

Without a return value preserving a potentially added new node passed back to the caller, you have to return the potential inserted node somehow. If you want a void result type, you need to pass the target pointer by address (Node **), or by reference (Node *&). Given this is tagged C++, I'd use the latter.

void Insert(Node*& root, int value) 
{
    if(root == NULL)
        root = CreateNode(value);

    else if(value <= root->value)
        Insert(root->left,value);

    else
        Insert(root->right,value);
}

Note that this always hangs duplicates on the left side of a node. To hang duplicates on the right side, change this:

    else if(value <= root->value)
        Insert(root->left,value);

to this:

    else if(value < root->value)
        Insert(root->left,value);

Finally, if you want unique keys in your tree (i.e., ignore duplicates) the following will do that:

void Insert(Node*& root, int value) 
{
    if(root == NULL)
        root = CreateNode(value);

    else if (value < root->value)
        Insert(root->left,value);

    else if (root->value < value)
        Insert(root->right, value);

    // else key is already present; do nothing.
}

This assumes a strict weak ordering of the key values, which exhibits the following property:

if (!(a<b || b<a))
    then  a == b

Best of luck.

BinaryTree Insertion

2 Answers2