Pattern this teaches:Binary Search Tree Problems
Delete Node in a BST
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 2
- Core for
- 2 roles
The problem
Given the root of a binary search tree and a key, delete the node with the given key while maintaining the BST property. Return the root of the updated BST. If the key is not found, return the unchanged tree.
Example 1
- Input
- root=[7,4,9,2,5,null,10], key=4
- Output
- [7,5,9,2,null,null,10]
- Why
- 4 has two children, so its inorder successor 5 takes its place.
Example 2
- Input
- root=[7,4,9,2,5,null,10], key=1
- Output
- [7,4,9,2,5,null,10]
- Why
- 1 is not in the tree, so nothing changes.
Example 3
- Input
- root=[], key=0
- Output
- []
- Why
- An empty tree has nothing to delete.
Constraints
- The number of nodes is in the range [0, 104].
- -105 <= Node.val <= 105
- All values are unique.
How to think about it
Updated 2026-09-29Finding the target node is standard binary search. The real problem is filling the hole it leaves behind: a leaf vanishes cleanly, a single-child node promotes its child, and a two-child node must be replaced by the smallest value in its right subtree so all order relations remain satisfied.
Approaches, worst first
Flatten, remove, and rebuild
time O(n) · space O(n)
Extract all values into a list via inorder traversal, drop the target key, and rebuild a height-balanced BST from the filtered array. Guarantees balance, but destroys existing tree topology and takes full linear time and space.
Standard Hibbard deletionWrite this one
time O(h) · space O(h)
Search down the tree. If node has 0 or 1 child, splice in its child. If it has two children, locate its inorder successor (minimum in right subtree), copy its value into the current node, and recursively delete the successor key from the right subtree.
Where people lose marks · 3
- Deleting the root node. When the deleted node has no parent, failing to return the promoted child causes callers to lose access to the new root.
- Successor deletion bug: deleting successor by searching from the entire root again rather than recursing specifically on `root.right` can lead to infinite loops or wrong nodes.
- Empty tree input: attempting to read `root.val` when root is null throws an error if not guarded immediately.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .