CODEWITHSUNDEEP
c++binary-search-tree
Franklinprogs
Franklinprogs

Reputation: 21

BinaryTree Insertion

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

Upvotes: 2

Views: 116

Answers (2)

WhozCraig
WhozCraig

Reputation: 66194

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.

Upvotes: 1

Nik Bougalis
Nik Bougalis

Reputation: 10613

You can do one of two things:

  1. 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.
  2. 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!
}

Upvotes: 2

Related Questions