Delete Node in a BST
Remove a key from a binary search tree and return the root: search for it, splice it out if it has at most one child, otherwise replace it with its inorder successor.
Problem Understanding
Delete Node in a BST: given the root of a binary search tree and a key, delete the node with that key (if present) and return the possibly updated root. The tree must still be a BST afterwards.
Examples: [5,3,6,2,4,null,7], key 3 → [5,4,6,2,null,null,7]; key 0 → unchanged; [], key 0 → [].
The Intuition: Three Cases at the Node
Finding the node is a plain BST search, the same walk as Validate Binary Search Tree relies on. Removing it depends on its children:
- Leaf: just remove it (return null to the parent).
- One child: that child's subtree takes its place.
- Two children: copy in its inorder successor, the smallest value on its right, then delete that successor from the right subtree. The successor has no left child, so that second delete is case 1 or 2.
The inorder order that makes the successor the right choice is the same one Kth Smallest Element in a BST counts through.
Interactive Walkthrough
DELETE 3 · OUTLINE = SUCCESSOR SEARCH
SEARCH FROM ROOT
deleting
3
call depth
0
Delete 3: search from the root as in any BST
Next
3 < 5: it can only be in the left subtree
BST
key
The node the current call is on is filled, the successor search is outlined, and the tree is redrawn after every change. Try Deep successor to see the search go left inside the right subtree.
Dry Run Table
Input: [5,3,6,2,4,null,7], key = 3.
| Step | Node | What happens |
|---|---|---|
| search | 5 | 3 < 5: go left |
| found | 3 | two children: successor is the leftmost of the right subtree, 4 |
| copy | 3 → 4 | the node now holds 4 |
| delete 4 | 4 (leaf) | removed from the right subtree |
Answer: [5,4,6,2,null,null,7].
The Solution Template
Each call returns the new root of its subtree, and the parent re-links it.
Delete Node in a BST Code
1var deleteNode = function(root, key) {2 if (!root) return null;3 if (key < root.val) {4 root.left = deleteNode(root.left, key);5 } else if (key > root.val) {6 root.right = deleteNode(root.right, key);7 } else {8 if (!root.left) return root.right;9 if (!root.right) return root.left;10 let succ = root.right;11 while (succ.left) succ = succ.left;12 root.val = succ.val;13 root.right = deleteNode(root.right, succ.val);14 }15 return root;16};
Edge Cases & Common Mistakes
- Deleting the root: works the same; the function returns the new root.
- Forgetting to reassign:
root.left = deleteNode(...), not just the call, or splices never reach the parent. - Key not present: the search reaches null and the tree is unchanged.
- Successor with a right child: deleting it is the one-child case; its right child moves up.
- Empty tree: return null.
Summary
Search by comparing with the key. At the node: return the other child if one is missing; otherwise copy in the inorder successor and delete it from the right subtree. O(h) time, O(h) stack.
More practice: DSA interview questions with answers · patterns cheat sheet