Delete Node in a BST

▶

Steps

setup

Start at root node 5

Begin the deletion process at the root node with value 5. The key to delete is 3, which is less than 5, so we will search the left subtree.

💡 Starting at the root is essential to traverse the BST correctly to find the node to delete.

Line:

if not root:
    return None
if key < root.val:

💡 The BST property guides the search direction for the key.

traverse

Recurse into left child node 3

Since key 3 is less than 5, recurse into the left child node with value 3 to continue searching for the node to delete.

💡 Recursion allows the algorithm to explore the subtree where the key might be found.

Line:

root.left = deleteNode(root.left, key)

💡 The recursive call moves the focus to the left subtree.

compare

Found node with value 3 to delete

At node 3, the key matches the node's value. This is the node to delete.

💡 Identifying the node to delete is the key step before handling deletion cases.

Line:

elif key == root.val:

💡 The algorithm now handles deletion cases for this node.

compare

Check if node 3 has no left child

Check if node 3 has no left child. It does have a left child (2), so this case does not apply.

💡 This check handles the case where the node has only a right child or no children.

Line:

if not root.left:

💡 Node 3 has a left child, so we must consider other deletion cases.

compare

Check if node 3 has no right child

Check if node 3 has no right child. It does have a right child (4), so this case does not apply.

💡 This check handles the case where the node has only a left child.

Line:

elif not root.right:

💡 Node 3 has both children, so we must find the inorder successor.

expand

Find inorder successor of node 3

Call helper function to find the inorder successor of node 3, which is the smallest node in its right subtree.

💡 The inorder successor replaces the node to maintain BST order after deletion.

Line:

successor = findSuccessor(root)

💡 The successor is node 4, the leftmost node in the right subtree of node 3.

insert

Replace node 3's value with successor's value 4

Replace the value of node 3 with the inorder successor's value 4 to maintain BST properties.

💡 Replacing the node's value avoids complex pointer rearrangements.

Line:

root.val = successor.val

💡 The node to delete now effectively has the successor's value.

delete

Delete successor node with value 4 in right subtree

Recursively delete the successor node with value 4 in the right subtree of the replaced node.

💡 Deleting the successor node removes the duplicate value from the tree.

Line:

root.right = deleteNode(root.right, successor.val)

💡 The recursive call focuses on the right subtree to remove the successor node.

delete

Delete leaf node 4 (successor)

At node 4 (successor), since it has no left child, return its right child (null), effectively deleting it.

💡 Deleting a leaf node is straightforward by returning null to its parent.

Line:

if not root.left:
    return root.right

💡 The successor node is removed from the tree.

return

Return updated subtree to parent node 3 (now 4)

Return null to node 3's right pointer, completing the deletion of the successor node. The subtree rooted at node 3 now has right child null.

💡 Returning updated subtrees maintains the BST structure after deletion.

Line:

return root

💡 The right subtree of node 3 is updated to reflect the deletion.

return

Return updated subtree to root node 5

Return the updated left subtree (rooted at node 4) to the root node 5, completing the deletion process.

💡 Returning the updated subtree to the root maintains the overall BST structure.

Line:

return root

💡 The root now points to the updated subtree with node 4 replacing node 3.

reconstruct

Final BST after deletion

The BST after deletion has node 4 replacing node 3, with the successor node removed. The tree maintains BST properties.

💡 The final structure confirms the correctness of the deletion algorithm.

Line:

return root

💡 The BST is correctly updated with the node deleted and replaced as needed.

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

def findSuccessor(node):
    curr = node.right  # STEP 6
    while curr.left:  # STEP 6 loop
        curr = curr.left
    return curr

def deleteNode(root, key):
    if not root:  # STEP 1
        return None
    if key < root.val:  # STEP 1-2
        root.left = deleteNode(root.left, key)  # STEP 2
    elif key > root.val:  # Not used in this example
        root.right = deleteNode(root.right, key)
    else:  # STEP 3
        if not root.left:  # STEP 4
            return root.right
        elif not root.right:  # STEP 5
            return root.left
        else:  # STEP 6
            successor = findSuccessor(root)  # STEP 6
            root.val = successor.val  # STEP 7
            root.right = deleteNode(root.right, successor.val)  # STEP 8
    return root  # STEP 10-11

📊

Delete Node in a BST - Watch the Algorithm Execute, Step by Step

Watching each recursive call and decision helps you understand how the BST properties are maintained during deletion.

Current node: 1

536247

DFS Stack

1 (entered)key=3

Current node: 2

536247

DFS Stack

2 (entered)key=31 (left_done)key=3

Current node: 2

536247

DFS Stack

2 (entered)key=31 (left_done)key=3

Current node: 2

536247

DFS Stack

2 (entered)key=31 (left_done)key=3

Current node: 2

536247

DFS Stack

2 (entered)key=31 (left_done)key=3

Current node: 5

536247

DFS Stack

5 (entered)2 (entered)key=31 (left_done)key=3

Return: {"successor_node_id":5}

Current node: 2

546247

DFS Stack

2 (entered)key=31 (left_done)key=3

Current node: 5

546247

DFS Stack

5 (entered)key=42 (entered)key=31 (left_done)key=3

Current node: 5

546247

DFS Stack

5 (entered)key=42 (entered)key=31 (left_done)key=3

Current node: 2

546247

DFS Stack

2 (returning)key=31 (left_done)key=3

Current node: 1

54627

DFS Stack

1 (returning)key=3

54627

Return: [5,4,6,2,null,null,7]

Key Takeaways

✓ The recursive search guided by BST properties efficiently locates the node to delete.

Without visualization, it's hard to see how recursion narrows down the search path.

✓ Replacing a node with its inorder successor preserves BST order after deletion.

This insight is subtle in code but clear when watching the successor being found and replacing the node.

✓ Deleting the successor node recursively handles the duplicate value cleanly.

The recursive deletion of the successor node is a key step that can be overlooked without step-by-step tracing.

Practice

1. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

2. You are given a binary tree and need to determine if it satisfies the property that for every node, all nodes in its left subtree have smaller values and all nodes in its right subtree have larger values, with no duplicates allowed. Which approach guarantees an optimal solution to this problem?

easy

A. Check each node by comparing it only with its immediate children recursively.

B. Apply a greedy algorithm that validates nodes as soon as they are visited.

C. Use dynamic programming to store subtree min and max values and combine results bottom-up.

D. Perform an inorder traversal and verify that the node values are strictly increasing.

Solution

1. Step 1: Understand BST property

   The BST property requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater, strictly increasing in inorder traversal.

2. Step 2: Recognize inorder traversal pattern

   Inorder traversal of a valid BST produces a strictly increasing sequence of values, so verifying this sequence guarantees correctness efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal yields sorted values for BST [OK]

Hint: Inorder traversal of BST is strictly increasing [OK]

Common Mistakes:

• Only comparing node with immediate children
• Using greedy checks without global ordering
• Confusing subtree min/max with inorder sequence

3. Consider the following buggy code snippet for finding the kth smallest element in a BST. Which line contains the subtle bug that can cause incorrect results or runtime errors?

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

# Bug introduced: k is used as zero-based index (count == k-1) instead of one-based

medium

A. Line with 'if count == k - 1:'

B. Line with 'count += 1'

C. Line with 'stack.append(current)'

D. Line with 'current = current.right'

Solution

1. Step 1: Identify the off-by-one bug

   The condition uses 'count == k - 1' which treats k as zero-based, but k is one-based in problem definition.

2. Step 2: Consequence of bug

   This causes the function to return the (k-1)th smallest element or miss the kth element, leading to incorrect results or runtime errors if k=1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct condition must be 'count == k' to match one-based indexing [OK]

Hint: Check indexing base for k carefully [OK]

Common Mistakes:

• Using zero-based index for k
• Misplacing count increment
• Returning too early

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. 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