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.