Full lesson preview

Delete a node from a BST

Remove a node with a given key from a binary search tree and return the new root.

Python practice16 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

Given the root of a Binary Search Tree (BST) and an integer key, delete the node with the given key in the BST. Return the root of the modified BST. If the key is not found, return the original tree. The BST property must be preserved after deletion.

Task

Implement deletion in a BST handling cases: leaf, one child, two children, and non-existent keys.

Examples

Delete a leaf node

Input

root = build_bst([5,3,7,2,4,6,8]); key = 2 result = inorder(delete_node(root, 2))

Output

[3, 4, 5, 6, 7, 8]

2 is a leaf. After deletion, the inorder traversal no longer includes 2.

Input format

The function delete_node(root, key) receives the root of a BST (or None) and an integer key.

Output format

Return the root of the BST after deletion. For testing, inorder(root) (a list) will be compared.

Constraints

- The BST contains unique integer values. - You must preserve BST properties. - Aim for average O(h) time where h is the tree height.

Samples

Sample 1

Input

delete_node(build_bst([5,3,7,2,4,6,8]), 3)

Output

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

Node 3 has two children; it is replaced by its inorder successor 4.