On this page

Delete Node in a Bst

Given the root of a BST and a key, delete the node with that key (if it exists) and return the root of the updated BST. The result must still be a valid BST.

Constraints:

  • The number of nodes is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5 and all values are unique.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

First find the node, using the usual BST search. The hard part is removing it. There are three cases, depending on how many children it has:

  • No children (a leaf): just remove it.
  • One child: the child takes its place.
  • Two children: we need to keep both subtrees. Every value in the right subtree is larger than every value in the left subtree, so we can hang the entire right subtree under the rightmost node of the left subtree, and then let the left child replace the deleted node.

For example, deleting 4: its left child is 2 and its right child is 6. The rightmost node of 4's left subtree is 2, so 6 becomes the right child of 2, and 2 replaces 4 under 8.

Approach: Find the Parent, Then Rewire

  1. If the root itself holds the key, return helper(root).
  2. Otherwise walk down with a pointer cur. At each step look at the child that would hold the key: if key < cur.val check cur.left, else cur.right. When that child's value equals the key, replace the child with helper(child) and stop.
  3. Return the original root.

helper(node) returns the subtree that should take the node's place:

  • No left child: return node.right.
  • No right child: return node.left.
  • Both exist: find the rightmost node of the left subtree with findLastRight, set its right to node.right, and return node.left.

The rewiring keeps order intact because the right subtree is entirely larger than anything in the left subtree.

Code

class Solution {
TreeNode* findLastRight(TreeNode* node) {
while (node->right != nullptr) node = node->right;
return node;
}
TreeNode* helper(TreeNode* node) {
if (node->left == nullptr) return node->right;
if (node->right == nullptr) return node->left;
TreeNode* rightChild = node->right;
TreeNode* lastRight = findLastRight(node->left);
lastRight->right = rightChild;
return node->left;
}
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
if (root->val == key) return helper(root);
TreeNode* cur = root;
while (cur != nullptr) {
if (key < cur->val) {
if (cur->left != nullptr && cur->left->val == key) {
cur->left = helper(cur->left);
break;
}
cur = cur->left;
} else {
if (cur->right != nullptr && cur->right->val == key) {
cur->right = helper(cur->right);
break;
}
cur = cur->right;
}
}
return root;
}
};

Complexity

Time: O(h)

Finding the node takes O(h), and findLastRight walks down one more path of at most O(h).

Space: O(1)

The solution is iterative and rewires pointers in place.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"I first find the node using the BST property, tracking its parent. Then I handle three cases. With no left child, the right child takes its place. With no right child, the left child takes its place. With two children, I keep both subtrees: every value on the right is larger than everything on the left, so I find the rightmost node of the left subtree, attach the entire right subtree as its right child, and let the left child replace the deleted node. The parent's pointer is updated to that returned subtree. The walk is one path plus one more descent, so time is O of h, and it is done in place with O of one extra space."
Next TopicKth Smallest Element in a BST