Returning structure pointer

Question

I'm confused with code below:

struct node* newNode(int data) 
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data  = data;
  node->left  = NULL;
  node->right = NULL;

  return(node);
}

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));  
  else
  {
    /* 2. Otherwise, recur down the tree */
    if (data <= node->data) 
        node->left  = insert(node->left, data);
    else
        node->right = insert(node->right, data);

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

newNode returns a pointer to the structure it has allocated. However in line 6 of the insert function the return value of newNode is not being assigned to anything, it's just being called. How is the code further down able to use the newly created node structure?

I will include that in my answer @ThunderWiring, if you don't mind! — gsamaras, Sep 13 '15 at 14:36

score 2 · Answer 1 · edited May 23 '17 at 11:58

2

Code below will run, if the tree is NOT empty. So, when the code in step .2 runs, the code in step .1 does not.

When the recursion unwinds, you can see that the assign operation is happening, for example:

node->left  = insert(node->left, data);

Oh and as ThunderWiring said, do not cast malloc!

edited May 23 '17 at 11:58

Community

1
1

answered Sep 13 '15 at 14:10

gsamaras

71,951
46
188
305

Code will run even if the tree is empty: it just creates a new top level node. – Serge Ballesta Sep 13 '15 at 15:03
Correct @SergeBallesta. – gsamaras Sep 13 '15 at 18:12

score 0 · Accepted Answer · answered Sep 13 '15 at 14:41

That is the interesting part of recursion!

The result of newNode is assigned to either node->left or node->right. Take this tree for instance:

    2
   / \
  1   NA

(note: NA = Not Available = NULL)

Now you want to add 3:

you pass to insert the root(i.e the node with key 2 above) and then the function gets to this line node->right = insert(node->right, data); (try to understand why yourself!)

which calls to insert again with node NA which eventually gets to the line return(newNode(data)); The returned result is assigned to node NA after the recursion back-tracks.

Eventually' you'll have this tree:

    2
   / \
  1   3

score 0 · Answer 3 · answered Sep 13 '15 at 15:02

What you have is an ordered tree.

You can create the tree by passing a NULL pointer, and you will get the top node. Next, when you add new items, they will be automatically inserted in correct place. But beware the structure of the tree will heavily depend on the insertion order.

If works, because on line 6 of insert function, the return value of newNode, is returned to caller. If node was initially NULL, it is expected that the programmer is creating a top node with something like:

struct node *top = insert(NULL, data);

So the return value of newNode will finally be assigned to pointer top.

When you insert a value in an existing tree, you will recurse down the tree until you find a node that has a NULL in its left (resp. right) field, and the newly created node will be assigned to that (previously NULL) field.

Returning structure pointer

3 Answers3