algoadvance

You are given the root of a binary search tree (BST) and an integer key. You need to delete the node with the value key in the BST and ensure that the BST property is maintained. Return the root of the modified BST.

Example:

Given the root of the tree as:
       5
      / \
     3   6
    / \   \
   2   4   7

And key = 3.

You should return the new root of the BST:
       5
      / \
     4   6
    /     \
   2       7

Note:

• The BST ensures that each node’s left subtree contains only nodes with keys less than the node’s key, and its right subtree contains only nodes with keys greater than the node’s key.
• There may be duplicate values in the tree, but we will only delete the first occurrence of the key.

Clarifying Questions

1. Q: Should we handle the case where the key does not exist in the BST? A: Yes, if the key does not exist in the BST, simply return the original root.

2. Q: What should be done if the BST is empty? A: If the BST is empty (i.e., the root is None), then return None.

3. Q: Are there any constraints on the size of the BST? A: No specific constraints are given, but it is reasonable to assume that the BST can be large.

Strategy

To delete a node in a BST, there are three primary cases to consider:

1. The node to be deleted is a leaf: In this case, simply remove the node.
2. The node to be deleted has one child: In this case, replace the node with its child.
3. The node to be deleted has two children: In this case, replace the node with its in-order successor (the smallest value in the right subtree) or in-order predecessor (the largest value in the left subtree).

Let’s outline the code to handle each of these cases.

Code

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

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        # Helper function to find the minimum node in a BST
        def findMin(node):
            while node.left:
                node = node.left
            return node

        # Base case: if the tree is empty
        if not root:
            return root
        
        if key < root.val:
            # If key is smaller than root's key, it lies in left subtree
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            # If key is greater than root's key, it lies in right subtree
            root.right = self.deleteNode(root.right, key)
        else:
            # Node to be deleted is found
            if not root.left:
                # Node with only one child or no child
                return root.right
            elif not root.right:
                # Node with only one child or no child
                return root.left
            
            # Node with two children: Get the in-order successor (smallest in the right subtree)
            temp = findMin(root.right)
            
            # Copy the in-order successor's content to this node
            root.val = temp.val
            
            # Delete the in-order successor
            root.right = self.deleteNode(root.right, temp.val)
            
        return root

Time Complexity

• Searching for the node to be deleted: O(h) where h is the height of the tree.
• Deleting the node and rearranging: O(h) in the worst case.

Therefore, the overall time complexity is O(h), where h is the height of the tree. In the worst case, this can be O(n) for an imbalanced tree, and O(log n) for a balanced tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?