450. Delete Node in a BST

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

Python

Steps

Find the target node
If target node at leaf, delete it
If target node has children, replace it with the Max(left) or Min(right)

Replace with Min Right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return

        if root.val == key:
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            min_node = self.find_min(root.right)
            root.right = self.deleteNode(root.right, min_node.val)

            min_node.left = root.left
            min_node.right = root.right

            root = min_node

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

        elif root.val < key:
            root.right = self.deleteNode(root.right, key)

        return root


    def find_min(self, node):
        if not node:
            return
        cur = node
        while cur.left:
            cur = cur.left
        return cur

Replace with Max Left
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return

        if root.val == key:
            if not root.left:
                return root.right
            if not root.right:
                return root.left

            max_node = self.find_max(root.left)
            root.left = self.deleteNode(root.left, max_node.val)

            max_node.left = root.left
            max_node.right = root.right

            root = max_node

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

        elif root.val < key:
            root.right = self.deleteNode(root.right, key)

        return root

    def find_max(self, node):
        if not node:
            return
        cur = node
        while cur.right:
            cur = cur.right

        return cur

Python​

Python