Delete Node in a BST

📋

Problem

Imagine managing a dynamic directory of contacts where you need to remove entries efficiently while maintaining sorted order for quick lookup.

Given the root of a binary search tree (BST) and a key, delete the node with the given key in the BST. Return the root node of the BST after deletion. The deletion must maintain the BST property.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique.The key is guaranteed to be in the BST.

Edge cases: Deleting a leaf node → simply remove itDeleting a node with only one child → replace node with childDeleting the root node → tree root changes

</>

IDE

def deleteNode(root: TreeNode, key: int) -> TreeNode:public TreeNode deleteNode(TreeNode root, int key)TreeNode* deleteNode(TreeNode* root, int key)function deleteNode(root, key)

def deleteNode(root, key):
    # Write your solution here
    pass

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* deleteNode(TreeNode* root, int key) {
    // Write your solution here
    return nullptr;
}

function deleteNode(root, key) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [5,3,6,2,4,null,7]Did not delete the node at all; returned original tree unchanged.✅ Add condition to detect node with key and perform deletion logic instead of returning root immediately.

Wrong: [5,3,6,2,4,null,7]Deleted node but did not update parent's child pointer, leaving dangling reference.✅ Assign root.left or root.right to recursive deleteNode call result to update parent's pointer.

Wrong: [5,3,6,2,4,null,7]Used inorder predecessor instead of successor for two-child node deletion.✅ Find inorder successor by traversing right child then leftmost path; replace node's value with successor's value.

Wrong: Stack overflow or timeoutImplemented exponential or linear scan instead of O(h) deletion; inefficient recursion or loops.✅ Use standard BST delete algorithm with O(h) complexity by searching key and deleting node recursively or iteratively.

✓

Test Cases

Focus on handling base cases and simple deletions before tackling edge cases.

Review inorder successor logic and pointer updates to avoid common pitfalls.

Ensure your solution runs efficiently on large inputs by analyzing time complexity.

t1_01basic

Input{"root":[5,3,6,2,4,null,7],"key":3}

Expected[5,4,6,2,null,null,7]

⏱ Performance - must finish in 2000ms

Node 3 has two children. Replace it with its inorder successor 4, then delete node 4.

💡 Recall the three cases when deleting a node in BST: leaf, one child, two children.

💡 For two children, find the inorder successor (smallest in right subtree) to replace the node.

💡 Replace node's value with successor's value, then delete the successor node recursively.

Why it failed: Failed to handle two-children case correctly: either did not find inorder successor or did not delete successor node properly. Fix by implementing successor search and recursive delete of successor.

✓ Correctly handles deletion of node with two children using inorder successor replacement.

t1_02basic

Input{"root":[5,3,6,2,4,null,7],"key":6}

Expected[5,3,7,2,4]

⏱ Performance - must finish in 2000ms

Node 6 has one child (7). Replace node 6 with its child 7.

💡 Check if node to delete has only one child and replace it directly with that child.

💡 If node has no left child, return right child; if no right child, return left child.

💡 Ensure recursive calls update parent's child pointers correctly.

Why it failed: Failed to handle one-child deletion case: did not replace node with its single child properly. Fix by returning the non-null child when one child is missing.

✓ Correctly deletes node with one child by replacing it with its child.

t2_01edge

Input{"root":[5],"key":5}

Expected[]

⏱ Performance - must finish in 2000ms

Deleting the only node (root) results in an empty tree.

💡 Consider the case when the tree has only one node which is the key to delete.

💡 Deleting this node should return None or empty tree.

💡 Return null when root matches key and has no children.

Why it failed: Did not handle single-node tree deletion correctly: failed to return null after deleting root. Fix by returning None when root matches key and has no children.

✓ Correctly deletes the root node when it is the only node in the tree.

t2_02edge

Input{"root":[5,3,null,2],"key":2}

Expected[5,3]

⏱ Performance - must finish in 2000ms

Deleting a leaf node (2) simply removes it without affecting other nodes.

💡 Leaf nodes have no children and can be removed by returning null.

💡 Ensure recursive calls update parent's child pointers to null when leaf is deleted.

💡 Check base case for leaf node deletion.

Why it failed: Failed to delete leaf node properly: did not set parent's child pointer to null. Fix by returning null when node is leaf and matches key.

✓ Correctly deletes leaf nodes by returning null.

t2_03edge

Input{"root":[5,3,6,2,null,null,7],"key":5}

Expected[6,3,7,2]

⏱ Performance - must finish in 2000ms

Deleting the root node (5) with two children replaces it with inorder successor (6).

💡 Deleting root node requires updating root reference.

💡 Use inorder successor to replace root value if root has two children.

💡 After replacement, delete the inorder successor node recursively.

Why it failed: Did not update root correctly after deletion: root value or reference not replaced properly. Fix by assigning root.val = successor.val and deleting successor node.

✓ Correctly deletes root node and updates root reference.

t3_01corner

Input{"root":[5,3,6,2,4,null,7],"key":4}

Expected[5,3,6,2,null,null,7]

⏱ Performance - must finish in 2000ms

Deleting a leaf node (4) to catch bug where successor is incorrectly chosen for leaf deletion.

💡 Deleting leaf nodes should not involve finding inorder successor.

💡 Check if node has zero children before attempting successor replacement.

💡 Return null directly when leaf node matches key.

Why it failed: Incorrectly finds and replaces with inorder successor even for leaf nodes. Fix by only finding successor when node has two children.

✓ Correctly deletes leaf nodes without unnecessary successor replacement.

t3_02corner

Input{"root":[5,3,6,2,4,null,7],"key":3}

Expected[5,4,6,2,null,null,7]

⏱ Performance - must finish in 2000ms

Deleting node with two children to catch bug where predecessor is used instead of successor.

💡 BST deletion requires replacing node with inorder successor (smallest in right subtree), not predecessor.

💡 Verify successor is found by traversing right child then leftmost path.

💡 Ensure replacement value is successor.val, not predecessor.val.

Why it failed: Used inorder predecessor instead of successor for two-child deletion. Fix by finding leftmost node in right subtree as successor.

✓ Correctly uses inorder successor for two-child node deletion.

t3_03corner

Input{"root":[5,3,6,2,4,null,7],"key":7}

Expected[5,3,6,2,4]

⏱ Performance - must finish in 2000ms

Deleting a leaf node at rightmost position to catch bug where right subtree pointer not updated.

💡 Ensure parent's right child pointer is updated when deleting rightmost leaf.

💡 Check recursive return values propagate correctly to parent.

💡 Verify no dangling pointers remain after deletion.

Why it failed: Failed to update parent's right pointer after deleting rightmost leaf. Fix by assigning root.right = deleteNode(root.right, key).

✓ Correctly updates parent's pointers after deleting rightmost leaf.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"key":50}

Expectednull

⏱ Performance - must finish in 2000ms

Deleting node in a BST with n=100 nodes to test O(h) time complexity. Must complete within 2 seconds.

💡 BST deletion runs in O(h) where h is tree height; balanced tree height ~ log n.

💡 Avoid unnecessary traversals or repeated subtree reconstructions.

💡 Use recursion or iteration with parent pointers to achieve O(h) time.

Why it failed: Solution exceeds time limit due to exponential or linear scans instead of O(h) deletion. Fix by implementing standard BST delete with recursion or iteration.

✓ Solution runs within time limit using O(h) BST deletion algorithm.

Practice

1. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

2. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

3. You are given a binary search tree and a target integer k. You need to determine if there exist two distinct nodes in the BST whose values sum up to k. Which of the following approaches guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to get a sorted array, then use two pointers to find if a pair sums to k.

B. Use dynamic programming to store sums of all subtree pairs and check for k.

C. Perform a brute force nested traversal of all node pairs directly on the BST without extra storage.

D. Use a greedy approach by always choosing the smallest and largest node values and adjusting pointers.

Solution

1. Step 1: Understand BST property and inorder traversal

   Inorder traversal of a BST produces a sorted array of node values.

2. Step 2: Apply two-pointer technique on sorted array

   Using two pointers at start and end, we can efficiently find if two values sum to k in O(n) time and O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder + two pointers is optimal and uses BST ordering [OK]

Hint: Inorder traversal yields sorted array for two-pointer sum [OK]

Common Mistakes:

• Trying nested loops directly on BST nodes without flattening
• Assuming greedy approach works without sorting
• Using DP which is unnecessary here

4. Consider the following Python code implementing BST validation using inorder traversal. What is the output of the program when run with the given test cases?

easy

A. true followed by false

B. true followed by true

C. false followed by true

D. false followed by false

Solution

1. Step 1: Trace first tree (2,1,3)

   Inorder traversal yields [1,2,3], strictly increasing, so returns true.

2. Step 2: Trace second tree (5,1,4 with children 3 and 6)

   Inorder traversal yields [1,5,3,4,6], 3 < 5 violates BST property, so returns false.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First tree valid BST, second invalid due to subtree violation [OK]

Hint: Inorder traversal must be strictly increasing [OK]

Common Mistakes:

• Assuming subtree root comparison is enough
• Confusing output order
• Missing strict inequality check

5. Suppose the BST can contain duplicate values and the range is inclusive [low, high]. How should the trimming algorithm be modified to correctly handle duplicates without breaking BST properties?

hard

A. Change all comparisons to strict inequalities (e.g., < low to <= low) to exclude duplicates outside range.

B. Rebuild the BST from scratch after filtering duplicates to ensure correct ordering.

C. Adjust pruning conditions to include nodes equal to low or high by using <= and >= comparisons appropriately.

D. Ignore duplicates during pruning since BST properties guarantee uniqueness.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on left or right subtree depending on implementation; inclusive range means nodes equal to low or high must be kept.

2. Step 2: Modify pruning conditions

   Use <= and >= in comparisons to keep nodes equal to boundaries, ensuring duplicates within range remain.

3. Step 3: Avoid rebuilding

   Rebuilding wastes time and space; pruning with adjusted conditions preserves BST and duplicates correctly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inclusive pruning keeps duplicates at boundaries [OK]

Hint: Use inclusive comparisons to keep duplicates within range [OK]

Common Mistakes:

• Using strict inequalities excludes boundary duplicates
• Rebuilding unnecessarily wastes resources