Binary Search Tree Insert & Deletion Operation


  • 0
    F
    
    // C function to search a given key in a given BST
    struct node* search(struct node* root, int key)
    {
        // Base Cases: root is null or key is present at root
        if (root == NULL || root->key == key)
           return root;
        
        // Key is greater than root's key
        if (root->key < key)
           return search(root->right, key);
     
        // Key is smaller than root's key
        return search(root->left, key);
    }
    
    struct node* insert(struct node* node, int key)
    {
        /* If the tree is empty, return a new node */
        if (node == NULL) return newNode(key);
     
        /* Otherwise, recur down the tree */
        if (key < node->key)
            node->left  = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);   
     
        /* return the (unchanged) node pointer */
        return node;
    }
    
    struct node * minValueNode(struct node* node)
    {
        struct node* current = node;
     
        /* loop down to find the leftmost leaf */
        while (current->left != NULL)
            current = current->left;
     
        return current;
    }
    
    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;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.