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. You are given a sorted array of unique integers and need to construct a binary search tree with minimal height. Which approach guarantees the resulting tree is height-balanced and constructed in O(n) time?

easy

A. Use a divide-and-conquer recursion that picks the middle element as root and recursively builds left and right subtrees.

B. Insert elements one by one into an empty BST using standard BST insertion.

C. Use a greedy approach that always inserts the smallest remaining element as the left child.

D. Build a balanced BST by repeatedly merging two smaller balanced BSTs.

Solution

1. Step 1: Understand the problem constraints

   The input is a sorted array, and the goal is to build a height-balanced BST efficiently.

2. Step 2: Evaluate approaches

   Inserting elements one by one leads to skewed trees and O(n^2) time. Greedy insertion of smallest elements does not guarantee balance. Merging BSTs is not straightforward and inefficient. The divide-and-conquer approach picks the middle element as root, ensuring balanced subtrees and O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Middle element chosen recursively -> balanced BST in O(n) time [OK]

Hint: Middle element recursion ensures balanced BST [OK]

Common Mistakes:

• Thinking inserting one by one is efficient
• Assuming greedy insertion balances tree

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

4. What is the worst-case time complexity of the optimized iterative DFS with BST pruning approach for computing the range sum of a BST with n nodes and height h?

medium

A. O(h) because only nodes along the height are visited

B. O(log n) because pruning skips most nodes

C. O(n) because in worst case pruning does not skip any nodes

D. O(n log n) because each node may be visited multiple times due to stack operations

Solution

1. Step 1: Identify worst-case scenario

   Worst case occurs when all nodes fall within the range or pruning is ineffective, so all n nodes are visited.

2. Step 2: Analyze time complexity

   Each node is processed once, so time complexity is O(n). Stack operations are O(1) amortized per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Worst case is full traversal, O(n) time [OK]

Hint: Worst case equals full traversal of all nodes [OK]

Common Mistakes:

• Assuming pruning always reduces to O(log n)
• Confusing height h with number of nodes n

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