deepSWE.io

Delete Node in a BST

Trees

Problem Statement

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.

Example

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

Output: [5,4,6,2,null,null,7]

Algorithm Explanation

Deleting a node in a BST has three cases, depending on the number of children the node to be deleted has.

Algorithm Steps

Find the Node: First, we need to find the node with the given key. We can do this with a standard BST search.
Case 1: Node is a Leaf: If the node has no children, we can simply remove it.
Case 2: Node has one child: If the node has one child, we can replace the node with its child.
Case 3: Node has two children: This is the most complex case. We need to find the node's in-order successor (the smallest node in its right subtree) or its in-order predecessor (the largest node in its left subtree). We then replace the node's value with the successor's/predecessor's value and recursively delete the successor/predecessor.

Start

Deleting node with key 3

Delete Node in a BST Solution


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            
            # Find the minimum value in the right subtree
            curr = root.right
            while curr.left:
                curr = curr.left
            root.val = curr.val
            root.right = self.deleteNode(root.right, root.val)
            
        return root