CODEWITHSUNDEEP
linked-listbinary-search-tree
linpohsien
linpohsien

Reputation: 15

Deleting a node in BST

The code below is are this website

I have some problems with a part of the code here. I have problem with this line:

root->left = deleteNode(root->left, key);

Why I cannot use simply deleteNode(root->left, key); here? I want to ask what the function of root->left in this line!

code

/* Given a binary search tree and a key, this function deletes the key
   and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
    // base case
    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

Upvotes: 0

Views: 48

Answers (1)

shani klein
shani klein

Reputation: 344

First of all you need to noticed that the function is not void so you cannot simply use deleteNode(root->left, key).

If I understant correct you want to know what is the returned value and why you put it inside the left (or right) node.

If you didn't get to the node you want to delete root->left = deleteNode(root->left, key); is like using `deleteNode(root->left, key), i.e - just go left .

After you find the node you want to delete there are few options: 1. if you got to node with only one child or no child you update the node value to this one child . So by type root->left = deleteNode(root->left, key); you update this value .

  1. if there is two sons you you find the inorder successor ( and it is a leaf) and "swap" between there values and than you delete the leaf. so now root->left = deleteNode(root->left, key); means you update the value to the successor and delete the node.

I hope it was helpfull .

Upvotes: 1

Related Questions