Delete Node in a BST
Delete Node in a BST is a medium trees & bst problem solved with the bst basics pattern.
The best approach, optimal (recursive delete with in-order successor), runs in O(h) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rebuild from in-order) up.
Problem
You are given the root of a binary search tree and an integer key. Remove the node whose value is key, if there is one, and return the root of the resulting tree (which may be a different node than before).
The tree you return must still be a valid binary search tree holding all the other values. When the deleted node has two children there is more than one correct shape; any valid result is accepted.
Examples
Example 1
- Input
root = [8, 3, 12, 1, 6, null, 15], key = 3- Output
[8, 6, 12, 1, null, null, 15]- Why
- Node 3 has two children. Its in-order successor 6 takes its place. [8, 1, 12, null, 6, null, 15] is also accepted.
Example 2
- Input
root = [8, 3, 12, 1, 6, null, 15], key = 10- Output
[8, 3, 12, 1, 6, null, 15]- Why
- 10 is not in the tree, so nothing changes.
Example 3
- Input
root = [], key = 4- Output
[]- Why
- Deleting from an empty tree leaves it empty.
Constraints
- The tree has
0to10^4nodes. -10^5 <= Node.val, key <= 10^5- All node values are distinct, and
rootis a valid binary search tree.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (rebuild from in-order) | O(n) | O(n) |
| Optimal (recursive delete with in-order successor) | O(h) | O(h) |
1Brute force (rebuild from in-order)
O(n)Every node is visited once by the traversal and created once by the rebuild, even though only one node had to go.O(n)The list of values plus a whole new tree.An in-order walk of a BST lists its values in sorted order. Collect every value except the key, then build a fresh balanced BST from that sorted list.
- Do an in-order traversal and append every value that is not equal to key.
- Build a BST from the sorted list: the middle element becomes the root, the left half the left subtree, the right half the right subtree.
- Return the new root (null if the list is empty).
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
List<Integer> vals = new ArrayList<>();
collect(root, key, vals);
return build(vals, 0, vals.size() - 1);
}
private void collect(TreeNode node, int key, List<Integer> vals) {
if (node == null) return;
collect(node.left, key, vals);
if (node.val != key) vals.add(node.val);
collect(node.right, key, vals);
}
private TreeNode build(List<Integer> vals, int lo, int hi) {
if (lo > hi) return null;
int mid = (lo + hi) / 2;
TreeNode node = new TreeNode(vals.get(mid));
node.left = build(vals, lo, mid - 1);
node.right = build(vals, mid + 1, hi);
return node;
}
}class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
vals: List[int] = []
self.collect(root, key, vals)
return self.build(vals, 0, len(vals) - 1)
def collect(self, node: Optional[TreeNode], key: int, vals: List[int]) -> None:
if node is None:
return
self.collect(node.left, key, vals)
if node.val != key:
vals.append(node.val)
self.collect(node.right, key, vals)
def build(self, vals: List[int], lo: int, hi: int) -> Optional[TreeNode]:
if lo > hi:
return None
mid = (lo + hi) // 2
node = TreeNode(vals[mid])
node.left = self.build(vals, lo, mid - 1)
node.right = self.build(vals, mid + 1, hi)
return nodeclass Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
vector<int> vals;
collect(root, key, vals);
return build(vals, 0, (int)vals.size() - 1);
}
private:
void collect(TreeNode* node, int key, vector<int>& vals) {
if (!node) return;
collect(node->left, key, vals);
if (node->val != key) vals.push_back(node->val);
collect(node->right, key, vals);
}
TreeNode* build(const vector<int>& vals, int lo, int hi) {
if (lo > hi) return nullptr;
int mid = (lo + hi) / 2;
TreeNode* node = new TreeNode(vals[mid]);
node->left = build(vals, lo, mid - 1);
node->right = build(vals, mid + 1, hi);
return node;
}
};function deleteNode(root, key) {
const vals = [];
const collect = (node) => {
if (node === null) return;
collect(node.left);
if (node.val !== key) vals.push(node.val);
collect(node.right);
};
const build = (lo, hi) => {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
const node = new TreeNode(vals[mid]);
node.left = build(lo, mid - 1);
node.right = build(mid + 1, hi);
return node;
};
collect(root);
return build(0, vals.length - 1);
}2Optimal (recursive delete with in-order successor)
O(h)One path down to the node plus one path down to its successor, where h is the tree height (log n when balanced, n when skewed).O(h)The recursion stack is at most the height of the tree.Walk down using the BST order. When you reach the node: if it has at most one child, return that child to its parent. If it has two children, copy the smallest value of its right subtree into it and then delete that value from the right subtree, which removes a node with at most one child.
- If root is null, return null.
- If key < root.val, set root.left = deleteNode(root.left, key); if key > root.val, do the same on the right.
- Otherwise this is the node: if it has no left child return root.right; if it has no right child return root.left.
- Two children: find the leftmost node of root.right, copy its value into root, then root.right = deleteNode(root.right, that value).
- Return root.
class Solution {
public 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;
}
}class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.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 = self.deleteNode(root.right, succ.val)
return rootclass Solution {
public:
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;
}
};function deleteNode(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;
let succ = root.right;
while (succ.left !== null) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}Edge cases to test
- The key is not in the tree
- Deleting the root, including a root with a single node
- Deleting a leaf, a node with only a left child, a node with only a right child
- Deleting a node with two children whose successor has a right subtree
Hints
Hint 1
Use the BST order to walk to the node: go left when key is smaller, right when it is larger.
Hint 2
A node with zero or one child is easy: replace it with that child (or with null).
Hint 3
For two children, copy in the smallest value of the right subtree (the in-order successor), then delete that value from the right subtree.
FAQ
What is the best time complexity for Delete Node in a BST?
Optimal (recursive delete with in-order successor) runs in O(h) time and O(h) extra space. One path down to the node plus one path down to its successor, where h is the tree height (log n when balanced, n when skewed).
Which pattern does Delete Node in a BST use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Delete Node in a BST?
Yes. Brute force (rebuild from in-order) takes O(n) time and O(n) space. An in-order walk of a BST lists its values in sorted order.
Which edge cases should I test for Delete Node in a BST?
The key is not in the tree; Deleting the root, including a root with a single node; Deleting a leaf, a node with only a left child, a node with only a right child; Deleting a node with two children whose successor has a right subtree.