Binary Search Tree Insert & Deletion Operation

  • 0
    // 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
            // node with only one child or no child
            if (root->left == NULL)
                struct node *temp = root->right;
                return temp;
            else if (root->right == NULL)
                struct node *temp = root->left;
                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.