Log inSign up
mediumLeetCodeNot Started

Delete Node in a BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given a root node reference of a Binary Search Tree (BST) and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Deleting a node from a BST consists of two stages: 1. Search for a node to remove. 2. If the node is found, delete the node while preserving the BST properties.

There are 3 cases when deleting a node: - Case 1 (No children / Leaf node): Simply remove the node by returning null. - Case 2 (One child): Replace the node with its non-empty child. - Case 3 (Two children): Find the inorder successor (smallest node in the right subtree) or inorder predecessor (largest node in the left subtree), copy its value to the target node, and recursively delete the successor/predecessor from the respective subtree.

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -105 <= Node.val <= 105
  • Each node has a unique value.
  • root is a valid binary search tree.
  • -105 <= key <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the three structural cases of binary search tree deletion.
  • Understand why the inorder successor or predecessor preserves the BST invariant.
  • Implement both recursive value-replacement and iterative pointer-rewiring approaches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Remove a specific key from a BST.
  • Maintain binary search tree invariant after node removal.
  • Preserve balance/connections.

Algorithmic Decision Tree:

  • If key < root.val: recurse root.left = deleteNode(root.left, key).
  • If key > root.val: recurse root.right = deleteNode(root.right, key).
  • If key == root.val: handle 0, 1, or 2 children cases.

Connected Patterns:

Insert into a Binary Search TreeInorder Successor in BSTTrim a Binary Search Tree

1. Flatten to Sorted Array, Remove Key, Rebuild Balanced BST

Intuition

Perform an inorder traversal to obtain an array of sorted values. If the key exists, filter it out. Then reconstruct a balanced BST using the midpoint divide-and-conquer algorithm. While correct, this takes O(N) time and O(N) auxiliary space, which destroys the O(H) efficiency expected for BST operations.

When to apply: Fallback approach when tree structural rebalancing is completely unmanaged.

Algorithm

  1. Extract all nodes via inorder traversal into an array, remove the target key, and reconstruct a new BST from the remaining sorted array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->val);
16 inorder(root->right, vals);
17 }
18
19 TreeNode* build(const std::vector<int>& vals, int l, int r) {
20 if (l > r) return nullptr;
21 int mid = l + (r - l) / 2;
22 TreeNode* node = new TreeNode(vals[mid]);
23 node->left = build(vals, l, mid - 1);
24 node->right = build(vals, mid + 1, r);
25 return node;
26 }
27public:
28 TreeNode* deleteNode(TreeNode* root, int key) {
29 std::vector<int> vals;
30 inorder(root, vals);
31
32 std::vector<int> filtered;
33 for (int v : vals) {
34 if (v != key) filtered.push_back(v);
35 }
36
37 return build(filtered, 0, (int)filtered.size() - 1);
38 }
39};
40
41int main() {
42 TreeNode* root = new TreeNode(5);
43 root->left = new TreeNode(3);
44 root->right = new TreeNode(6);
45 root->left->left = new TreeNode(2);
46 root->left->right = new TreeNode(4);
47 root->right->right = new TreeNode(7);
48
49 Solution sol;
50 TreeNode* res = sol.deleteNode(root, 3);
51 std::cout << "New Root: " << res->val << " (Left: " << res->left->val << ", Right: " << res->right->val << ")" << std::endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Iterative Pointer Splicing (Pure Rewiring)

Intuition

Find the node to delete and its parent using iterative BST search. If the node has 0 or 1 child, update parent.left or parent.right to point to the child. If the node has 2 children, find its inorder successor and successor's parent, rewire the pointers to place the successor in the node's position, and attach the subtrees.

When to apply: When node values are immutable or objects cannot be copied.

Algorithm

  1. Search for target and parent iteratively; splice child pointers without copying node values.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* deleteNode(TreeNode* root, int key) {
13 TreeNode* curr = root;
14 TreeNode* parent = nullptr;
15
16 while (curr && curr->val != key) {
17 parent = curr;
18 if (key < curr->val) curr = curr->left;
19 else curr = curr->right;
20 }
21
22 if (!curr) return root; // Key not found
23
24 // Helper to replace curr with child under parent
25 auto replaceChild = [&](TreeNode* child) {
26 if (!parent) return child; // Deleting root
27 if (parent->left == curr) parent->left = child;
28 else parent->right = child;
29 return root;
30 };
31
32 // Case 1 & 2: 0 or 1 child
33 if (!curr->left) return replaceChild(curr->right);
34 if (!curr->right) return replaceChild(curr->left);
35
36 // Case 3: 2 children. Find successor (min in right subtree)
37 TreeNode* succParent = curr;
38 TreeNode* succ = curr->right;
39 while (succ->left) {
40 succParent = succ;
41 succ = succ->left;
42 }
43
44 // Copy successor value
45 curr->val = succ->val;
46
47 // Delete successor (has at most 1 right child)
48 if (succParent->left == succ) {
49 succParent->left = succ->right;
50 } else {
51 succParent->right = succ->right;
52 }
53
54 return root;
55 }
56};
57
58int main() {
59 TreeNode* root = new TreeNode(5);
60 root->left = new TreeNode(3);
61 root->right = new TreeNode(6);
62 root->left->left = new TreeNode(2);
63 root->left->right = new TreeNode(4);
64 root->right->right = new TreeNode(7);
65
66 Solution sol;
67 TreeNode* res = sol.deleteNode(root, 3);
68 std::cout << "New Root: " << res->val << " (Left: " << res->left->val << ", Right: " << res->right->val << ")" << std::endl;
69 return 0;
70}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

3. Standard Recursive BST Deletion with Inorder Successor

Intuition

1. If root == null, return null. 2. If key < root.val, root.left = deleteNode(root.left, key). 3. If key > root.val, root.right = deleteNode(root.right, key). 4. If key == root.val: - If !root.left, return root.right (handles 0 children and 1 right child). - If !root.right, return root.left (handles 1 left child). - Otherwise, find min node in right subtree: minNode = getMin(root.right). - Assign root.val = minNode.val. - Recursively delete the successor: root.right = deleteNode(root.right, minNode.val). 5. Return root.

When to apply: Standard gold standard for technical interviews and clean maintainable code.

Algorithm

  1. Search via BST recursion; on match, handle 0/1 child immediately, or replace value with successor and delete successor from right subtree.

BST Node Deletion Simulation (2 Children Case)

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Search moves left from 5 to 3
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
deleteNode(5, 3): 3 < 5 -> call deleteNode(5.left, 3)
Decision / next transition
1
Why this step matters

Search moves left from 5 to 3.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 TreeNode* findMin(TreeNode* node) {
12 while (node->left) node = node->left;
13 return node;
14 }
15public:
16 TreeNode* deleteNode(TreeNode* root, int key) {
17 if (!root) return nullptr;
18
19 if (key < root->val) {
20 root->left = deleteNode(root->left, key);
21 } else if (key > root->val) {
22 root->right = deleteNode(root->right, key);
23 } else {
24 // Found target node
25 // Case 1 & 2: 0 or 1 child
26 if (!root->left) {
27 TreeNode* rightChild = root->right;
28 delete root;
29 return rightChild;
30 }
31 if (!root->right) {
32 TreeNode* leftChild = root->left;
33 delete root;
34 return leftChild;
35 }
36
37 // Case 3: 2 children
38 TreeNode* minRight = findMin(root->right);
39 root->val = minRight->val;
40 root->right = deleteNode(root->right, minRight->val);
41 }
42 return root;
43 }
44};
45
46int main() {
47 TreeNode* root = new TreeNode(5);
48 root->left = new TreeNode(3);
49 root->right = new TreeNode(6);
50 root->left->left = new TreeNode(2);
51 root->left->right = new TreeNode(4);
52 root->right->right = new TreeNode(7);
53
54 Solution sol;
55 TreeNode* res = sol.deleteNode(root, 3);
56 std::cout << "New Root: " << res->val << " (Left: " << res->left->val << ", Right: " << res->right->val << ")" << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) recursion call stack

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Flatten to Sorted Array, Remove Key, Rebuild Balanced BSTO(N)O(N)Extract all nodes via inorder traversal into an array, remove the target key, and reconstruct a new BST from the remaining sorted array.O(N)
2.Iterative Pointer Splicing (Pure Rewiring)O(H) where H is tree heightO(1) auxiliary spaceSearch for target and parent iteratively; splice child pointers without copying node values.O(H) where H is tree height
3.Standard Recursive BST Deletion with Inorder SuccessorOptimalO(H) where H is tree heightO(H) recursion call stackSearch via BST recursion; on match, handle 0/1 child immediately, or replace value with successor and delete successor from right subtree.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Memory leak in C++

Splicing nodes without calling delete on deleted nodes when manual memory management is expected.

Searching for successor in the left subtree

The successor is the minimum of the RIGHT subtree, not left.

Failing to reassign child references

Calling deleteNode(root.left, key) without assigning root.left = deleteNode(...) fails to detach the deleted child from its parent.

Crucial Edge Cases to Validate:

  • Key not found in the BST — Tree remains unchanged; gracefully returns root without null pointer exceptions.
  • Deleting the root of a single-node tree — Successfully returns null.
  • Deleting a leaf node — Returns null to the parent caller, splicing out the node cleanly.
  • Deleting the root of a large tree with 2 children — Successor replaces the root value and old root is deleted.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify the 3 cases with the interviewer immediately before writing code: Leaf, 1 child, 2 children.
  2. State why the inorder successor has at most 1 child, proving that deleting the successor will not cause a secondary 2-child cascade.
  3. Note that both Inorder Successor (min of right) and Inorder Predecessor (max of left) are valid choices.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does replacing a node with its inorder successor preserve the BST invariant?

2.What is the maximum number of children that an inorder successor of a node can have?

3.What is the time complexity of deleting a node from a completely skewed BST of N nodes?

Back to DSA Sheet