Delete Node in a BST

Question (LC.450)

Given the root of a BST and a key to delete, return the root of the tree with the key deleted.

Example

I: root = [5,3,6,2,4,null,7], key = 3

       5
     /   \ 
    3     6 
  /   \    \ 
 2     4    7

O: [5,4,6,2,null,null,7] or [5,2,6,null,4,null,7] 

promote from left subtree 

       5
     /   \ 
    2     6 
     \     \ 
      4     7

promote from right subtree 

       5
     /   \ 
    4     6 
  /        \ 
 2          7
 

Note: The replacing node has to be the largest from the left subtree or the smallest from the right subtree. The immediate child won't work. Check out deleting 5 for example.

Analysis

Deletion is an O(h) operation in BST. That means cannot divide and conquer 2 subtrees. We can only recurse down one path. So simply inserting the entire subtree won't work. We have to promote the next up median value to replace the current root.

D&C Code

If you can do the insertion with D&C, then deletion can be done in the same way.

def findLargest(self, root: TreeNode) -> TreeNode:

    if root is None:
        return None 
    
    if root.right is not None:
        return self.findLargest(root.right)
    else:
        return root 

def findSmallest(self, root: TreeNode) -> TreeNode:
    
    if root is None:
        return None 
    
    if root.left is not None:
        return self.findSmallest(root.left)
    else:
        return root 


def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    
    # base 
    
    if root is None:
        return None
    
    
    # divide 
    
    if key == root.val:
        
        # perform deletion
        
        
        # 3 cases 
        
        if root.left is None and root.right is None:
            return None
        
        if root.left is None and root.right is not None:
            return root.right 
        
        if root.left is not None and root.right is None:
            return root.left 
        
        # promote largest in the left subtree 
        # or the smallest in the right subtree 
        
        # largest_left_tree = self.findLargest(root.left)    
        # root.val = largest_left_tree.val 
        # root.left = self.deleteNode(root.left, largest_left_tree.val)
                
        smallest_right_tree = self.findSmallest(root.right)
        root.val = smallest_right_tree.val 
        root.right = self.deleteNode(root.right, smallest_right_tree.val)
        
        # return the promoted subtree 
        return root 
        
        
    elif key < root.val:
        
        root.left = self.deleteNode(root.left, key)
        
        return root
    else: # k > root.val
        
        root.right = self.deleteNode(root.right, key)
    
        return root 

Complexity

Time - 2 parts searching the delete key and searching for the replacement value. The worst case is something like this

                      20 
                     /  \
                    5    25
                        /  \ 
                      (22)  30 
                              \ 
                               35
                              /   \
                            34     40 
                            

Say we want to delete 20 and using the smallest on the right subtree replacement strategy. If 22 exists, then we just delete it and it is a leaf node. The worst case is that the next node is the smallest node. Then we have to cascade the delete to 25, to 30, 35, and eventually a leaf node. The base case for the deletion is O(1). Finding the replacement value and cascading the delete will be the height of the tree. Therefore, O(h).

Space - Find the smallest or largest value in BST can be done without recursion. The pure deletion is just O(h).