CODEWITHSUNDEEP
cpointersdata-structuresbinary-search-tree
user1005284
user1005284

Reputation:

Return pointer to node in insert method of binary search tree

I would like to know why we have to return the pointer to root node in insert function of BST. Wouldn't the BST be updated even if we don't return the pointer to root node, since we are updating the data in the memory, to which the pointer is mapped? The following code

struct node* insert(struct node* node, int data) 
{
    /* 1. If the tree is empty, return a new, single node */
    if (node == NULL)    
        return(newNode(data));

    /* 2. Otherwise, recurse down the tree */
    else
    {
        if (data <= node->data)
            node->left  = insert(node->left, data);
        else
            node->right = insert(node->right, data);

        /* return the (unchanged) node pointer */
        return node;
    }
}

Upvotes: 0

Views: 2792

Answers (3)

Meet Sinojia
Meet Sinojia

Reputation: 131

As others have suggested, it is just a part of algorithm, otherwise node->left = insert(node->left, data); would not work.

Here is an algorithm (in C/C++) that does not return anything:

void Insert(struct node** node, int key)
{
    if(*node == NULL) *node = newNode(key);
    else insert(*node, key);
}

void insert(struct node* node, int key)
{
    if (key < node->key)
    {
        if(node->left == NULL) node->left = newNode(key);
        else insert(node->left, key);
    }

    else if (key > node->key)
    {
        if(node->right == NULL) node->right = newNode(key);
        insert(node->right, key);
    }
}

Here, newNode(key) is a function that creates a new node and set its key value as supplied in the argument.

Note that using only theinsert function given at the bottom would do the job, except for when node is NULL (that is, the tree is empty). That is why I have used separate Insert function to handle this case.

You would insert elements as:

Insert(&root,50);

I hope this clarifies your doubt.

Upvotes: 0

Toby Liu
Toby Liu

Reputation: 1267

In this implementation, the function must return a node or else the recursion will break. Your conditional says to reassign either the node->left or node->right pointer to the result of a recursive call. So it is eventually going to expect a node value to be returned.

If you took the return statement out, I do not think this code would compile.

Upvotes: 0

user3553031
user3553031

Reputation: 6214

In the case where the caller passed in a empty tree (null pointer), this function must return a pointer to the tree so that the caller now has a non-empty tree. In the case where the tree is non-empty, the function recurses and returns a new sub-tree at some point. You could write a version of this code that returned NULL (or some other value) if the root node did not change, but that would make the code more complicated. This is the simplest way to do it.

Upvotes: 2

Related Questions