Return pointer to node in insert method of binary search tree

Question

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;
    }
}

node->left/right = insert would not work properly if insert didn't return the node. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Aug 2, 2014 at 19:58
Its part of the chosen algorithm. That node pointer has to come from somewhere. You don't need to do any of this if you use a different algorithm, such as using a pointer-to-pointer and no recursion. — WhozCraig
– WhozCraig, Commented Aug 2, 2014 at 20:27
Does this code do the same, except that this will not return a pointer?? struct node* insert(struct node* node, int data) { /* 1. If the tree is empty, return a new, single node / if (node == NULL) root =newNode(data); / 2. Otherwise, recurse down the tree */ else { if (data <= node->data) insert(node->left, data); else insert(node->right, data); } } — user1005284
– user1005284, Commented Aug 3, 2014 at 18:50

user3553031 · Accepted Answer · 2014-08-02 20:16:30Z

2

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.

answered Aug 2, 2014 at 20:16

user3553031

Sign up to request clarification or add additional context in comments.

Comments

Toby Liu · Accepted Answer · 2014-08-03 00:42:07Z

0

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.

answered Aug 3, 2014 at 0:42

Toby Liu

1,2779 silver badges14 bronze badges

Comments

Meet Sinojia · Accepted Answer · 2017-04-01 20:44:37Z

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.

Collectives™ on Stack Overflow

Return pointer to node in insert method of binary search tree

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related