Delete Node in a BST

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 deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0 Output: []

Could you solve it with time complexity O(height of tree)?

Deleting a Node in a Binary Search Tree

This problem asks us to delete a node with a given key from a Binary Search Tree (BST) and return the updated root of the BST. The key challenge lies in maintaining the BST properties after deletion.

1. Naive Approach

A simple but not very efficient approach would be to first search for the node to be deleted. Once found, replace it with either its inorder successor (smallest node in the right subtree) or its inorder predecessor (largest node in the left subtree). However, this approach can lead to unbalanced trees in certain deletion patterns, potentially degrading the performance of BST operations.

2. Optimal Solution

The optimal solution involves the following steps:

1. Search: Recursively search for the node to be deleted. If the key is smaller than the current node's value, go left; otherwise, go right.
2. Node Found:
   • Case 1: Node has no children (leaf node): Simply remove the node.
   • Case 2: Node has one child: Replace the node with its child.
   • Case 3: Node has two children: Find the inorder successor (minimum value in the right subtree) of the node. Replace the node's value with the inorder successor's value. Then, delete the inorder successor from the right subtree.

Here's a Python code implementation of the optimal solution:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Node found
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            # Node with two children
            successor = findMin(root.right)
            root.val = successor.val
            root.right = deleteNode(root.right, successor.val)
    
    return root

def findMin(node: TreeNode) -> TreeNode:
    while node.left:
        node = node.left
    return node

3. Big(O) Runtime Analysis

The time complexity of this solution is O(H), where H is the height of the BST.

• Search: The initial search for the node takes O(H) time in the worst case (when the BST is skewed).
• Deletion:
  • Case 1 (no children): O(1)
  • Case 2 (one child): O(1)
  • Case 3 (two children): Finding the inorder successor takes O(H) time in the worst case (if the right subtree is skewed). Deleting the inorder successor also takes O(H) time. In balanced BST, findMin usually takes O(log n) time

Therefore, the overall time complexity is dominated by the search and potential inorder successor operations, resulting in O(H). In the average case of a balanced BST, the height H is log(N), where N is the number of nodes, so the average time complexity is O(log N).

4. Big(O) Space Usage Analysis

The space complexity of this solution is O(H), where H is the height of the BST. This is due to the recursive calls on the call stack. In the worst-case scenario (skewed BST), H can be equal to N (the number of nodes), resulting in O(N) space complexity. In the average case (balanced BST), H is log(N), so the space complexity is O(log N).

5. Edge Cases

• Empty Tree: If the tree is empty (root is None), return None.
• Key Not Found: If the key is not found in the tree, the original tree should be returned without modification.
• Root Node Deletion: If the key is the same as the root node's value, the function must correctly handle the deletion of the root node and return the updated root.
• Duplicate Keys: The problem statement specifies that each node has a unique value. If duplicate keys were allowed, the algorithm would need to be modified to handle the case where there are multiple nodes with the same key.

Here are some edge case scenarios:

• Empty Tree:
  • Input: root = None, key = 5
  • Output: None
• Key Not Found:
  • Input: root = [5,3,6,2,4,None,7], key = 0
  • Output: [5,3,6,2,4,None,7] (original tree)
• Deleting Root (Leaf):
  • Input: root = [5], key = 5
  • Output: None
• Deleting Root (One Child):
  • Input: root = [5,3,None], key = 5
  • Output: [3]
• Deleting Root (Two Children):
  • Input: root = [5,3,6,2,4,None,7], key = 5
  • Output: A valid BST like [6,3,7,2,4,None,None] or [7,3,6,2,4,None,None]