Delete Node in a BST Python Solution

Tested Python solution for LeetCode 450 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 450, Medium. Topics: Tree, Binary Search Tree, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 450   # by problem number
lcpy gen -s delete_node_in_a_bst   # by problem name

​

Problem

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.

Note: When a node with two children is deleted, replacing it with either its inorder successor or predecessor is accepted.

​

Examples

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: One valid answer is [5,4,6,2,null,null,7]; [5,2,6,null,4,null,7] is also accepted.

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.

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

Follow up: Could you solve it with time complexity O(height of tree)?

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import TreeNode


class Solution:
    # Time: O(h) where h is the height of the tree
    # Space: O(h) recursion stack
    def delete_node(self, root: TreeNode[int] | None, key: int) -> TreeNode[int] | None:
        if root is None:
            return None

        if key < root.val:
            root.left = self.delete_node(root.left, key)
        elif key > root.val:
            root.right = self.delete_node(root.right, key)
        else:
            # Node found: handle deletion by child count.
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            # Two children: replace value with inorder successor, delete successor.
            successor = root.right
            while successor.left is not None:
                successor = successor.left
            root.val = successor.val
            root.right = self.delete_node(root.right, successor.val)
        return root

​

Complexity

Time	Space
O(h) where h is the height of the tree	O(h) recursion stack

​

Tags

NeetCode 250, NeetCode All.