Delete Node in BST

Implement standard BST deletion with all three cases handled recursively.

binary-search-tree tree-traversal recursion

You are given the root of a binary search tree (BST) represented as nested dictionaries with keys 'val', 'left', 'right' (where 'left' or 'right' can be None). Write a function `delete_node_bst(root, key)` that removes the node with the given key from the BST and returns the new root (as a nested dict or None). The BST property must be preserved: for any node, all values in its left subtree are strictly less, and all values in its right subtree are strictly greater. Assume all keys are unique. If the key is not present, return the original tree unchanged. The function must handle all three deletion cases: a leaf node, a node with one child, and a node with two children. For the two-child case, replace the node's value with its inorder successor (the smallest node in the right subtree) and remove that successor from the right subtree. The root may change if the deleted node was the root.

Constraints

The tree is a valid BST. The number of nodes is between 0 and 10^4. Node values are integers. The key is an integer. Time complexity should be O(H) where H is the height of the tree (in the worst case H equals the number of nodes). Space complexity O(H) for recursion stack.

Example

>>> tree = {'val': 5, 'left': {'val': 3, 'left': None, 'right': {'val': 4, 'left': None, 'right': None}}, 'right': {'val': 6, 'left': None, 'right': None}}
>>> tree = delete_node_bst(tree, 3)
>>> tree
{'val': 5, 'left': {'val': 4, 'left': None, 'right': None}, 'right': {'val': 6, 'left': None, 'right': None}}

>>> tree = {'val': 5, 'left': {'val': 3, 'left': None, 'right': None}, 'right': {'val': 6, 'left': None, 'right': None}}
>>> tree = delete_node_bst(tree, 7)
>>> tree
{'val': 5, 'left': {'val': 3, 'left': None, 'right': None}, 'right': {'val': 6, 'left': None, 'right': None}}

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Traverse the tree recursively: if key is less than current node's value, go left; if greater, go right.

If the node to delete has two children, find the minimum value in its right subtree (by going left repeatedly), copy that value into the node, then delete that minimum value from the right subtree.

After recursion, return the (possibly updated) current node so the parent's child pointer updates correctly.

The base case is when the current node is None: the key is not present, return None.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.