Problem Description

You are given the root node of a Binary Search Tree (BST) and a key value. Your task is to delete the node containing the given key from the BST and return the root node reference of the modified tree.

The deletion process involves two main steps:

1. Find the node with the value equal to the given key
2. Remove the node from the tree while maintaining the BST property

When deleting a node from a BST, there are three cases to consider:

• 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 an appropriate replacement (either the inorder predecessor or inorder successor) and restructure the tree

The BST property must be preserved after deletion: for any node, all values in its left subtree must be less than the node's value, and all values in its right subtree must be greater than the node's value.

The function should return the root of the modified BST. If the key doesn't exist in the tree, return the original tree unchanged. If the root itself is deleted, return the new root of the tree.

For example:

• If you have a BST with nodes [5, 3, 6, 2, 4, null, 7] and need to delete key 3, the resulting tree could be [5, 4, 6, 2, null, null, 7] or [5, 2, 6, null, 4, null, 7], both maintaining the BST property.

Intuition

To delete a node from a BST, we need to think about how to maintain the tree structure and BST property after removal. Let's think through this step by step.

First, we need to locate the node to delete. Since it's a BST, we can use binary search - if the key is smaller than current node's value, go left; if larger, go right. This naturally leads to a recursive approach.

Once we find the node to delete, we face the critical question: what should replace this node? This depends on how many children the node has:

If the node has no children, it's simple - we just remove it by returning None.

If the node has only one child, we can simply "skip over" the node being deleted and connect its parent directly to its child. The child subtree already maintains the BST property relative to the ancestors.

If the node has two children, this is where it gets interesting. We can't just pick either child to replace the node because that would leave us with an orphaned subtree. We need a strategy that preserves all nodes and maintains the BST ordering.

The key insight is that we can use either the inorder predecessor (rightmost node in the left subtree) or the inorder successor (leftmost node in the right subtree) as a replacement. Why? Because these nodes have special properties:

• The inorder successor is the smallest value larger than the node being deleted
• The inorder predecessor is the largest value smaller than the node being deleted

The solution uses the inorder successor approach. Here's the clever part: instead of replacing values and then deleting the successor node (which would require another deletion operation), we can restructure the tree directly. We find the leftmost node in the right subtree, attach the entire left subtree of the deleted node to this successor's left, and then promote the right subtree to replace the deleted node.

This works because:

• The leftmost node in the right subtree has no left child (by definition)
• All values in the original left subtree are smaller than any value in the right subtree
• This maintains the BST property throughout the tree

The beauty of this recursive solution is that each recursive call handles one node and returns the (possibly modified) subtree rooted at that node, making the tree updates clean and automatic.

Solution Approach

The implementation uses a recursive approach to traverse the BST and handle the deletion. Let's walk through the code step by step:

1. Base Case - Empty Tree:

if root is None:
    return None

If we reach a None node, it means the key doesn't exist in the tree, so we return None.

2. Searching for the Node to Delete:

if root.val > key:
    root.left = self.deleteNode(root.left, key)
    return root
if root.val < key:
    root.right = self.deleteNode(root.right, key)
    return root

• If the current node's value is greater than the key, the target must be in the left subtree
• If the current node's value is less than the key, the target must be in the right subtree
• We recursively call deleteNode on the appropriate subtree and update the child pointer
• This ensures the tree structure is maintained as we traverse and modify

3. Node Found - Deletion Cases:

When root.val == key, we've found the node to delete. Now we handle the three cases:

Case 1: Node has no left child

if root.left is None:
    return root.right

Simply return the right child (which could be None if it's a leaf node).

Case 2: Node has no right child

if root.right is None:
    return root.left

Simply return the left child.

Case 3: Node has both children

node = root.right
while node.left:
    node = node.left
node.left = root.left
root = root.right
return root

This is the most complex case:

• First, find the inorder successor (leftmost node in the right subtree) by starting at root.right and going left as far as possible
• Attach the entire left subtree of the node being deleted to the successor's left pointer: node.left = root.left
• Replace the deleted node with its right subtree: root = root.right
• Return the new root of this subtree

Why this works:

• The successor node initially has no left child (we went as far left as possible)
• All nodes in the original left subtree are smaller than the successor
• All nodes in the right subtree maintain their relative positions
• The BST property is preserved throughout

Time Complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this is O(n).

Space Complexity: O(h) for the recursion stack. In the worst case, this is O(n) for a skewed tree, but O(log n) for a balanced tree.

Example Walkthrough

Let's walk through deleting node with value 5 from this BST:

Initial Tree:
       8
      / \
     5   10
    / \    \
   3   6    11
  /     \
 2       7

Step 1: Search for node 5

• Start at root (8): Since 5 < 8, go left
• Found node 5 - this is our target

Step 2: Node 5 has two children (3 and 6) This is Case 3, so we need to find the inorder successor in the right subtree.

Step 3: Find inorder successor

• Start at node 5's right child (6)
• Go left as far as possible: 6 has no left child, so 6 is our successor

Step 4: Restructure the tree

• Attach node 5's left subtree to successor's left: node(6).left = node(3)
• Replace node 5 with its right subtree (rooted at 6)

After attaching left subtree to successor:
     6
    / \
   3   7
  /
 2

This subtree replaces node 5:
       8
      / \
     6   10
    / \    \
   3   7    11
  /
 2

Step 5: Return the modified tree The BST property is maintained:

• All values in 6's left subtree (2, 3) are less than 6
• All values in 6's right subtree (7) are greater than 6
• The relationship with parent node 8 is preserved

Another Example - Deleting a leaf node: If we delete node 2 from the result above:

• Search: 8 → 6 → 3 → 2
• Node 2 has no children (Case 1)
• Simply return None to parent
• Parent (3) updates its left pointer to None

Final tree after deleting 2:

       8
      / \
     6   10
    / \    \
   3   7    11

Solution Implementation

Time and Space Complexity

Time Complexity: O(h) where h is the height of the tree, or O(log n) for a balanced BST and O(n) for a skewed BST where n is the number of nodes.

The algorithm traverses from the root to find the target node, which takes O(h) time. When the target node is found and has two children, it finds the minimum node in the right subtree (successor), which also takes at most O(h) time. The key operations are:

• Finding the target node: O(h)
• Finding the successor (minimum in right subtree): O(h)
• Reorganizing the tree structure: O(1)

Since these operations are sequential, the total time complexity is O(h) + O(h) + O(1) = O(h).

Space Complexity: O(h) where h is the height of the tree.

The space complexity is determined by the recursive call stack. In the worst case, the recursion goes as deep as the height of the tree before finding the target node or reaching a null node. Each recursive call uses O(1) space for its parameters and local variables, and there can be at most h recursive calls on the stack simultaneously, resulting in O(h) space complexity.

For a balanced BST, this would be O(log n), and for a completely skewed tree, this would be O(n).

Common Pitfalls

1. Modifying Tree Structure Without Updating Parent References

A common mistake is attempting to delete a node without properly updating the parent's reference to it. Consider this incorrect approach:

# INCORRECT - doesn't update parent's reference
def deleteNode(self, root, key):
    if root is None:
        return None
  
    if root.val == key:
        # Handle deletion cases
        if root.left is None:
            return root.right
        # ... other cases
  
    # Just traversing without updating connections
    if root.val > key:
        self.deleteNode(root.left, key)  # ❌ Not updating root.left
    else:
        self.deleteNode(root.right, key)  # ❌ Not updating root.right
  
    return root

Why it fails: The recursive calls don't update the parent-child relationships, leaving dangling references to deleted nodes.

Solution: Always reassign the child pointers with the return value of recursive calls:

root.left = self.deleteNode(root.left, key)   # ✅ Updates connection
root.right = self.deleteNode(root.right, key)  # ✅ Updates connection

2. Incorrect Inorder Successor Replacement Logic

When dealing with a node that has two children, developers often make mistakes in how they handle the successor node:

# INCORRECT - loses nodes in the process
def deleteNode(self, root, key):
    # ... finding the node ...
  
    if root.val == key:
        if root.left and root.right:
            # Find successor
            successor = root.right
            while successor.left:
                successor = successor.left
          
            # ❌ Wrong: Simply replacing value loses subtree structure
            root.val = successor.val
            # Now we have duplicate values in the tree!

Why it fails: Simply copying the successor's value creates duplicates and doesn't properly remove the successor from its original position.

Better approaches:

1. Restructure approach (used in solution): Attach the left subtree to the successor and return the right subtree
2. Value replacement with recursive deletion: Replace the value and recursively delete the successor:

# Alternative correct approach
successor = root.right
while successor.left:
    successor = successor.left
root.val = successor.val
root.right = self.deleteNode(root.right, successor.val)

3. Not Handling Edge Cases Properly

Developers sometimes forget to handle special cases:

# INCORRECT - doesn't handle root deletion properly
def deleteNode(self, root, key):
    if root.val == key:
        # ❌ What if we're deleting the root itself?
        # Need to return the new root!
        if root.left is None and root.right is None:
            root = None  # This doesn't affect the caller's reference
    # ...

Solution: Always return the modified tree root, allowing the caller to update their reference:

# ✅ Correct: Return the new root
if root.left is None:
    return root.right  # Could be None for a leaf
if root.right is None:
    return root.left

4. Infinite Loop in Successor Finding

A subtle bug can occur if the successor-finding logic is implemented incorrectly:

# INCORRECT - potential infinite loop
node = root.right
while node:  # ❌ Wrong condition
    node = node.left
# node is now None!

Solution: Check for node.left existence, not just node:

node = root.right
while node.left:  # ✅ Correct: stops at the leftmost node
    node = node.left
# node is now the leftmost node with no left child