LeetCode 450: Delete Node in a BST

Problem Restatement

We are given the root of a binary search tree and an integer key.

We need to delete the node whose value equals key.

After deletion, the tree must still be a valid binary search tree.

Return the possibly updated root of the tree.

The root can change. For example, if we delete the original root, some other node may become the new root.

The official problem describes the task in two stages: first search for the node, then delete it if it exists. If the key is absent, the tree remains unchanged.

Input and Output

The node class is usually:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Examples

Example 1:

root = [5, 3, 6, 2, 4, None, 7]
key = 3

The tree is:

        5
       / \
      3   6
     / \   \
    2   4   7

After deleting 3, one valid result is:

        5
       / \
      4   6
     /     \
    2       7

Output:

[5, 4, 6, 2, None, None, 7]

Other valid BST shapes may also be accepted, as long as the node is deleted and the BST property remains valid.

Example 2:

root = [5, 3, 6, 2, 4, None, 7]
key = 0

The key does not exist.

The tree is unchanged.

Example 3:

root = []
key = 0

The answer is:

None

First Thought: Search Like a BST

To find the node, we use the BST property.

At a node:

This avoids scanning the whole tree when the tree is balanced.

The harder part is deletion.

Key Insight

Deleting a BST node has three cases.

The first two cases are simple.

If a node has no left child, its right child can take its place.

If a node has no right child, its left child can take its place.

The two-child case needs care.

For a node with two children, a valid replacement is the inorder successor.

The inorder successor is the smallest node in the right subtree.

It is found by starting at:

root.right

then moving left until no left child remains.

This node is larger than every value in the left subtree and smaller than or equal to every value in the right subtree, so it can replace the deleted node while preserving the BST property.

Algorithm

Define:

deleteNode(root, key)

If root is None, return None.

If:

key < root.val

delete from the left subtree:

root.left = deleteNode(root.left, key)

If:

key > root.val

delete from the right subtree:

root.right = deleteNode(root.right, key)

Otherwise, root.val == key, so delete this node.

If one child is missing:

if not root.left:
    return root.right

if not root.right:
    return root.left

If both children exist:

1. Find the smallest node in the right subtree.
2. Copy its value into root.
3. Delete that successor node from the right subtree.
4. Return root.

Correctness

The recursive search follows the BST property.

If key < root.val, the key can only appear in the left subtree, so modifying only root.left preserves the right subtree unchanged.

If key > root.val, the key can only appear in the right subtree, so modifying only root.right preserves the left subtree unchanged.

When the node is found, the deletion cases preserve the BST property.

If the node has no left child, returning the right child is valid because every node in that right subtree is larger than the deleted node and still fits in the deleted node’s position.

If the node has no right child, returning the left child is valid because every node in that left subtree is smaller than the deleted node and still fits in the deleted node’s position.

If the node has two children, the inorder successor is the smallest value in the right subtree. It is larger than every value in the left subtree and no larger than the remaining values in the right subtree. Replacing the deleted node’s value with the successor value keeps the BST ordering valid.

The successor is then deleted from the right subtree, so no duplicate node remains.

Therefore, the returned tree contains all original values except key, and it remains a valid BST.

Complexity

Here, h is the height of the BST.

For a balanced tree, h = O(log n).

For a skewed tree, h = O(n).

Implementation

class Solution:
    def deleteNode(
        self,
        root: 'Optional[TreeNode]',
        key: int,
    ) -> 'Optional[TreeNode]':
        if not root:
            return None

        if key < root.val:
            root.left = self.deleteNode(root.left, key)
            return root

        if key > root.val:
            root.right = self.deleteNode(root.right, key)
            return root

        if not root.left:
            return root.right

        if not root.right:
            return root.left

        successor = self._min_node(root.right)
        root.val = successor.val
        root.right = self.deleteNode(root.right, successor.val)

        return root

    def _min_node(self, node: 'TreeNode') -> 'TreeNode':
        while node.left:
            node = node.left

        return node

Code Explanation

The base case handles an empty subtree:

if not root:
    return None

If the key is smaller, we delete from the left subtree:

root.left = self.deleteNode(root.left, key)

If the key is larger, we delete from the right subtree:

root.right = self.deleteNode(root.right, key)

When root.val == key, this is the node to delete.

If the node has no left child:

return root.right

If the node has no right child:

return root.left

These two cases also cover leaf deletion, because a leaf has both children missing.

For the two-child case, we find the inorder successor:

successor = self._min_node(root.right)

Then copy its value:

root.val = successor.val

Now the current node has the correct replacement value, but the successor node still exists in the right subtree. So we delete it:

root.right = self.deleteNode(root.right, successor.val)

The helper finds the smallest node in a subtree:

while node.left:
    node = node.left

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    if not root:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def run_tests():
    s = Solution()

    root = TreeNode(
        5,
        TreeNode(3, TreeNode(2), TreeNode(4)),
        TreeNode(6, None, TreeNode(7)),
    )

    root = s.deleteNode(root, 3)
    assert inorder(root) == [2, 4, 5, 6, 7]

    root = TreeNode(
        5,
        TreeNode(3, TreeNode(2), TreeNode(4)),
        TreeNode(6, None, TreeNode(7)),
    )

    root = s.deleteNode(root, 0)
    assert inorder(root) == [2, 3, 4, 5, 6, 7]

    root = TreeNode(1)
    root = s.deleteNode(root, 1)
    assert root is None

    root = TreeNode(2, TreeNode(1), None)
    root = s.deleteNode(root, 2)
    assert inorder(root) == [1]

    root = TreeNode(2, None, TreeNode(3))
    root = s.deleteNode(root, 2)
    assert inorder(root) == [3]

    print("all tests passed")

run_tests()

Test meaning: