Delete Node in a BST — Solution in Python, Java & C++
Delete Node in a BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Delete Node in a BST is a medium coding problem on binary search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.
- Difficulty: Medium
- Topics: Binary Search, Trees, Recursion
- Asked at: Amazon, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values and an integer key. Remove the node holding key, if there is one, and return the root of the resulting tree, which must still be a binary search tree.
Several trees are valid after a deletion, so delete this way:
- a node with no children is simply removed;
- a node with one child is replaced by that child;
- a node with two children takes the value of its in-order successor (the smallest value in its right subtree), and then that successor is deleted from the right subtree by the same rules.
If no node holds key, return the tree unchanged.
Example 1
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Node 3 has two children, so it takes the value of its in-order successor 4 (the smallest value in its right subtree), and that leaf is removed.
Example 2
Input: root = [5,3,6,2,4,null,7], key = 5
Output: [6,3,7,2,4]
Explanation: The root's successor is 6; 6 moves up into the root and its old node is replaced by its only child 7.
Example 3
Input: root = [], key = 0
Output: []
Explanation: There is nothing to delete in an empty tree.
Constraints
The number of nodes in the tree is in the range [0, 10^4]-10^5 <= Node.val <= 10^5Each node has a unique valueroot is a valid binary search tree-10^5 <= key <= 10^5
Follow-up: Can you do it in O(height of tree) time?
Hints for Delete Node in a BST
Hint 1
First find the node: the search-tree order tells you at every step whether
keyis to the left or the right.Hint 2
Removing a leaf or a node with one child is easy — its parent simply points at the child (or at nothing). The hard case is a node with two children.
Hint 3
For two children, copy the in-order successor's value into the node (the leftmost node of its right subtree) and then delete that value from the right subtree; the successor has no left child, so that second deletion is one of the easy cases.
How to solve Delete Node in a BST
Write the deletion as a recursive function that returns the new root of the subtree it was given. Searching moves left or right by comparing with key; at the node itself, the number of children decides how it is removed.
Approach
- If the subtree is empty, return null — the key is not there.
- If
key < node.val, setnode.left = deleteNode(node.left, key); ifkey > node.val, do the same on the right. Returnnode. - Otherwise this is the node to delete. If it has no left child, return its right child; if it has no right child, return its left child.
- With two children, walk to the leftmost node of the right subtree, copy its value into
node, then setnode.right = deleteNode(node.right, thatValue).
Why it works
The in-order successor is larger than everything in the left subtree and smaller than everything else in the right subtree, so placing its value at the node keeps the search-tree order. The successor has no left child, so deleting it from the right subtree falls into the zero- or one-child case and does not cascade further.
Complexity
- Time —
O(h), where h is the height of the tree — one search path, plus one more down the right subtree - Space —
O(h) for the recursion
Pitfalls
- Return the subtree's new root from every call and assign it back to the parent's link — that is how a removed node actually disappears.
- Deleting the root itself must also work: the function's return value is the new root.
- Use the successor, as the statement fixes; using the in-order predecessor also gives a valid search tree, but a different one.
Reference solution
Python
from typing import Optional
def deleteNode(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
succ = root.right
while succ.left is not None:
succ = succ.left
root.val = succ.val
root.right = deleteNode(root.right, succ.val)
return rootJava
public static TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode succ = root.right;
while (succ.left != null) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}C++
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) root->left = deleteNode(root->left, key);
else if (key > root->val) root->right = deleteNode(root->right, key);
else {
if (!root->left) return root->right;
if (!root->right) return root->left;
TreeNode* succ = root->right;
while (succ->left) succ = succ->left;
root->val = succ->val;
root->right = deleteNode(root->right, succ->val);
}
return root;
}JavaScript
var deleteNode = function(root, key) {
if (root === null) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (root.left === null) return root.right;
if (root.right === null) return root.left;
var succ = root.right;
while (succ.left !== null) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search · Binary Trees and Tree Traversals