CODEWITHSUNDEEP
cbinary-search-tree
mahesh
mahesh

Reputation: 17

Binary tree deletion-cannot understand some pointers

I have a doubt in this binary tree deletion.The code is

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int key;
    struct node *left, *right;
};
struct node *newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}
struct node* insert(struct node* node, int key)
{
    if (node == NULL) return newNode(key);

    if (key < node->key)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}
struct node * minValueNode(struct node* node)
{
    struct node* current = node;
     while (current->left != NULL)
        current = current->left;

    return current;
}
struct node* deleteNode(struct node* root, int key)
{
   if (root == NULL) return root;

   if (key < root->key)
        root->left = deleteNode(root->left, key);
     else if (key > root->key)
        root->right = deleteNode(root->right, key);
   else
    {
        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;
        }

    struct node* temp = minValueNode(root->right);

         root->key = temp->key;

       root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int main()
{
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of the given tree \n");
    inorder(root);

    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    return 0;
}

The lines which I cannot understand is:

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

is this code actually return NULL value then can I rewrite the code as struct node *temp=NULL in both the cases but the last inorder value is not displayed when i do this.

Upvotes: 2

Views: 241

Answers (1)

John Bollinger
John Bollinger

Reputation: 181104

The code you are inquiring about is part of the code handling the case that the node to delete is the root node of the tree. It checks whether the root node has only one child (or zero), in which case the deletion can be performed simply by making the one child the new root of the tree.

Note in particular that when root->left == NULL it is the right child, not the left one, that is chosen as the new root (and temporarily recorded in temp), and vice versa. Either way, the original root node is freed since it is no longer in the tree, and will not be accessible via the new root pointer that the function is about to return.

The function returns NULL only when the root node is initially the only node in the tree.

Upvotes: 0

Related Questions