450.-delete-node-in-a-bst.md

450. Delete Node in a BST

• Medium

• 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.

Analysis

The problem here is about how we would be deleting the node after we found it. There are four cases for that:

1. If the node has no child, then we just have to delete it.
2. If the node has a left child but not a right one, then we would connect the the left child with the parent of the targetted node.
3. If the node has a right child but not a left one, then the above sceneraio still applies.
4. If the node has both right child and left child, then we have to find the successor to be put here. We can choose the number that is colsest to it but bigger. To find that value, we just have to go to the right child and then go left until we can't go left anymore. Then after the switch, we would end up with the scenario 1 or 3.

class Solution:
    def deleteNode(self, root, key):
        if not root: return None
        
        if root.val == key:
            if not root.right: return root.left
            
            if not root.left: return root.right
            
            if root.left and root.right:
                temp = root.right
                while temp.left: temp = temp.left
                root.val = temp.val
                root.right = self.deleteNode(root.right, root.val)

        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
            
        return root