The challenge
Remove one key from a strict BST and return the updated root.
Missing keys leave the tree unchanged. For two children, copy the inorder successor key and remove the successor.
Example
Deleting root 8 copies successor 10, then removes its original leaf. With one child, the root becomes 4.
Use the walkthrough below to inspect the input and each state change.
See BST deletion, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Key: 8
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Deletion returns a replacement subtree root for every structural case.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def bst_delete(root, key):
if root is None:
return None
if key < root.value:
root.left = bst_delete(root.left, key)
elif key > root.value:
root.right = bst_delete(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
successor = root.right
while successor.left:
successor = successor.left
root.value = successor.value
root.right = bst_delete(root.right, successor.value)
return root
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
Node* bst_delete(Node* root, long long key) {
if (!root) return nullptr;
if (key < root->value) root->left = bst_delete(root->left, key);
else if (key > root->value) root->right = bst_delete(root->right, key);
else {
if (!root->left || !root->right) {
Node* child = root->left ? root->left : root->right;
delete root; // Nodes must be individually allocated with new.
return child;
}
Node* successor = root->right;
while (successor->left) successor = successor->left;
root->value = successor->value;
root->right = bst_delete(root->right, successor->value);
}
return root;
}