Delete Node In A Bst - Leetcode Solution

Problem Statement:

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the function should first find the node to delete, and then delete it accordingly while preserving the properties of the BST.

Solution:

Approach:

The first step in solving the problem is to find the node to delete. After that, there are three cases to consider:

Case 1: If the node to delete is a leaf node (node with no children), simply delete it from the tree.

Case 2: If the node to delete has only one child, replace the node with its child.

Case 3: If the node to delete has two children, replace the node with its inorder successor or predecessor. The inorder predecessor is the largest node in the left subtree, while the inorder successor is the smallest node in the right subtree.

Algorithm:

1. If the root is None, return None.
2. If the root's value matches the key, then we need to delete this node.
3. If the key is less than the root's value, then the node to delete must be in the left subtree. Recursively call the delete function on the left subtree and update the left child of the root accordingly.
4. If the key is greater than the root's value, then the node to delete must be in the right subtree. Recursively call the delete function on the right subtree and update the right child of the root accordingly.
5. If the node to delete has both left and right children, then find its inorder successor or predecessor. If the inorder predecessor is found, then set the root value to the predecessor's value and recursively delete the predecessor in the left subtree. Similarly, if the inorder successor is found, then set the root value to the successor's value and recursively delete the successor in the right subtree.
6. If the node to delete has only one child, then replace the node with its child.
7. If the node to delete is a leaf node, simply delete it from the tree.

Implementation:

Here is the Python implementation of the above algorithm:

def deleteNode(root, key):
    if root is None:
        return None

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # node to delete found

        # Case 1: leaf node
        if root.left is None and root.right is None:
            return None

        # Case 2: node has only one child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        # Case 3: node has two children
        temp = root.right
        while temp.left:
            temp = temp.left

        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)

    return root

The time complexity of this algorithm is O(h), where h is the height of the BST. The worst-case time complexity of this algorithm is O(n) when the tree becomes a skewed tree.

1