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. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

2. You are given a binary tree where exactly two nodes have been swapped by mistake, violating the binary search tree property. Which approach guarantees an optimal solution to recover the tree without changing its structure or using extra space beyond a constant amount?

easy

A. Use a bottom-up dynamic programming approach to reconstruct the BST by comparing subtrees and swapping nodes.

B. Perform an inorder traversal, store values in a list, sort the list, then overwrite the tree nodes with sorted values.

C. Apply a greedy approach by swapping any two nodes that violate the BST property during a single inorder traversal pass.

D. Use Morris inorder traversal to detect the two swapped nodes during traversal and swap their values, achieving O(1) space complexity.

Solution

1. Step 1: Understand the problem constraints

   The problem requires recovering a BST where two nodes are swapped, without extra space and without changing the tree structure.

2. Step 2: Identify the approach that meets constraints

   Morris inorder traversal allows inorder traversal without recursion or stack, detecting swapped nodes on the fly and swapping their values, achieving O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Morris traversal is the only approach with O(1) space and no structural changes [OK]

Hint: Morris traversal enables O(1) space recovery [OK]

Common Mistakes:

• Assuming sorting values is optimal despite extra space
• Believing greedy single pass fixes all cases
• Confusing DP with tree recovery

3. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

4. What is the time complexity of the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

Hint: Time depends on tree height, not total nodes [OK]

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here

5. The following code attempts to find if there exist two distinct nodes in a BST whose values sum to k. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 6: dfs(node.left)

B. Line 4: if k - node.val in seen:

C. Line 7: seen.add(node.val)

D. Line 8: dfs(node.right)

Solution

1. Step 1: Understand DFS and set usage

   The code checks if complement exists in seen before adding current node's value.

2. Step 2: Identify bug in order of operations

   Checking complement before adding current node's value misses pairs where both nodes are the same, or misses valid pairs if current node's value is needed for complement checks in children.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Complement check must happen after adding current node's value to seen [OK]

Hint: Add current node to set before checking complements [OK]

Common Mistakes:

• Checking complement before adding current node's value
• Not handling None nodes properly
• Returning False too early