450.Delete_Node_in_a_BST(Medium).md

450. Delete Node in a BST (Medium)

Date and Time: Jul 23, 2024, 22:08 (EST)

Link: https://leetcode.com/problems/delete-node-in-a-bst/

Question:

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: [ ]

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].

• -10^5 <= Node.val <= 10^5

• Each node has a unique value.

• root is a valid binary search tree.

• -10^5 <= key <= 10^5

Walk-through:

1. we perform BST to search the key, if root.val > key we search root.left; if root.val < key we search root.right.

2. If we found the node, we check if the node has both children or not, if not, we can just return root.left or root.right. Otherwise, node has both children and we choose to search its right-subtree to find the deep-left node (the smallest val in the node's right-subtree) to replace node, so we first go to root.right, then repeat cur = root.left to find the deepest left node and set this value to be the root.val (root.val = cur.val) and set root.right to be self.deleteNode(root.right, root.val) to delete the duplicate in the original root.

My Solution:

# Definition for a binary tree node.
# 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: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        # Use Binary Search to find the key
        # Once we find the key, check its left and right, if both exists, go to the root's rigth branch deepest left node (find the next smallest element), and set it to be root.val (delete the key and maintain BST property), and delete this new root.val from the new root's right branch

        # TC: O(height of the tree), SC: O(1)
        if not root:
            return
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                # Replace root with the 2nd smallest one from the right branch's deep left node
                cur = root.right
                while cur.left:
                    cur = cur.left
                root.val = cur.val
                # Rebuild the new branch without the 2nd smallest
                root.right = self.deleteNode(root.right, root.val)
        
        return root

Time Complexity: $O(\text{height of tree})$
Space Complexity: $O(1)$