CODEWITHSUNDEEP
calgorithmbinary-treeavl-tree
JohnDotOwl
JohnDotOwl

Reputation: 3755

AVL / Binary Search Tree

I have a C programming question. The below is a insert to a node with a key.

I don't understand why node->left = insert(node->left,key)

I assume this code WILL update the node->left with what?

Isn't it calling insert() again? It's like calling the same function again and again isn't it a infinite loop or insert calling?

I checked a few example, they are all updating the node->left that way by calling the same function again? Let's say I misunderstood, what are the storing in it? The pointer? Or are they just magically linked?

// An AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};

struct node* insert(struct node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left  = insert(node->left, key);//This just called Insert function again?
    else
        node->right = insert(node->right, key);

Upvotes: 0

Views: 171

Answers (1)

Petr
Petr

Reputation: 9997

Yes, they are calling the insert function again, but note that the arguments have changed1. This is what is called recursion.

Also note that it does not always call the same function again: in case node==NULL it does not call it. So this is not infinite; as you take node->left, node->left->left and so one, you once come to a point where the pointer is NULL.

1 I don't say that recursive call must always change its arguments, but that's the most common approach.

Upvotes: 4

Related Questions