Deleting Nodes from a BST

The Three Cases of Deletion

Deleting a node from a BST is not as simple as just removing it. We must consider the node's children to decide how to "patch up" the tree. There are three distinct cases we need to handle:

1. The node has no children (it's a leaf node).
2. The node has exactly one child (either left or right).
3. The node has two children.

Let's break down each case.

Case 1: Deleting a Node with No Children

This is the simplest case. If the node to be deleted is a leaf, we can simply remove it. In a recursive implementation, this means the parent's pointer to that node is set to None.

Case 2: Deleting a Node with One Child

If the node has a single child, we can remove the node by "promoting" its child. The parent of the node to be deleted will now point directly to that node's single child, effectively bypassing the deleted node.

Case 3: The Tricky Case - Deleting a Node with Two Children

This is where the real challenge lies. If we remove a node with two children, we are left with two disconnected subtrees (the left and the right). We cannot simply promote one child, as that would leave the other subtree orphaned.

So, what value should replace the deleted node? To maintain the BST property, the replacement must be:

• Greater than every value in the left subtree.
• Less than every value in the right subtree.

There are two perfect candidates for this job:

1. The in-order successor: The smallest node in the right subtree.
2. The in-order predecessor: The largest node in the left subtree.

Using either will preserve the BST property. The most common strategy, and the one we will focus on, is using the in-order successor.

The strategy is as follows:

1. Find the in-order successor (the leftmost node in the right subtree).
2. Copy the successor's value to the node you intend to delete.
3. The original problem is now transformed: we must delete the successor node from the right subtree.
4. Crucially, the successor, being the smallest in its subtree, can have at most one child (a right child). This means the recursive deletion call will always fall into Case 1 or Case 2, which we already know how to solve!

A Visual and Conceptual Walkthrough

Before we jump into code, it's essential to have a solid mental model of this process. The following video provides an excellent conceptual breakdown of all three cases, with a focus on the in-order successor strategy for the two-child case.

Implementing the Deletion Algorithm

Now that you understand the strategy, let's look at how to implement it recursively in Python. The key to a recursive solution is that each call to the delete function on a subtree returns the new root of that modified subtree. The parent then uses this return value to update its left or right pointer.

This video continues from where the last one left off, walking through a concise and powerful implementation.

Full Implementation

Here is a full implementation within our BSTNode class, similar to the structure from the previous lesson. This code uses the in-order successor strategy.

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

    # We will reuse the insert method from the previous lesson
    def insert(self, val):
        if not self.val:
            self.val = val
            return
        if self.val == val:
            return
        if val < self.val:
            if self.left:
                self.left.insert(val)
            else:
                self.left = BSTNode(val)
        else:
            if self.right:
                self.right.insert(val)
            else:
                self.right = BSTNode(val)

    # In-order traversal to display the tree sorted
    def inorder(self, vals):
        if self.left is not None:
            self.left.inorder(vals)
        if self.val is not None:
            vals.append(self.val)
        if self.right is not None:
            self.right.inorder(vals)
        return vals

    def delete(self, val):
        # Base case: if the tree is empty
        if self is None or self.val is None:
            return self

        # Recursive search for the node to delete
        if val < self.val:
            if self.left:
                self.left = self.left.delete(val)
        elif val > self.val:
            if self.right:
                self.right = self.right.delete(val)
        else: # Node to be deleted is found
            # Case 1 & 2: Node has 0 or 1 child
            if self.left is None:
                return self.right
            if self.right is None:
                return self.left

            # Case 3: Node has two children
            # Find the in-order successor (smallest in the right subtree)
            min_node = self.right
            while min_node.left:
                min_node = min_node.left
            
            # Copy the successor's value to this node
            self.val = min_node.val
            
            # Recursively delete the successor from the right subtree
            self.right = self.right.delete(min_node.val)
            
        return self

# --- How to use it ---
nums = [15, 10, 20, 8, 12, 18, 25, 19]
bst = BSTNode()
for num in nums:
    bst.insert(num)

print("Original tree (sorted):", bst.inorder([]))

# Delete a leaf node (8)
bst.delete(8)
print("After deleting 8:", bst.inorder([]))

# Delete a node with one child (20) -> child 18 gets promoted
bst.delete(20)
print("After deleting 20:", bst.inorder([]))

# Delete the root node (15) -> replaced by successor 18
bst.delete(15)
print("After deleting 15 (root):", bst.inorder([]))

A Critical Detail: Notice the lines self.left = self.left.delete(val) and self.right = self.right.delete(val). This is one of the most important aspects of the recursive implementation. Simply calling self.left.delete(val) without re-assignment would not modify the tree structure. You must update the parent's pointer with the result of the deletion from the child's subtree.

Alternative Strategy and Exercise

As mentioned earlier, you can also use the in-order predecessor (the largest value in the left subtree) to replace a node with two children. The logic is perfectly symmetrical.

The codebasics channel provides another great explanation and sets up a perfect exercise for you to solidify your understanding.

This exercise is highly recommended. Implementing the alternative approach will prove that you've truly grasped the underlying principles of BST deletion.

Conclusion

In this lesson, we dissected the most complex of the basic BST operations. You learned that deleting a node requires analyzing its structure and handling three distinct cases to maintain the tree's integrity.

Key Takeaways:

• Deleting a node from a BST is handled in three cases depending on whether the node has zero, one, or two children.
• Cases with zero or one child are straightforward: you either remove the node or replace it with its single child.
• The two-child case is solved by replacing the node's value with its in-order successor (or predecessor) and then recursively deleting the successor.
• In a recursive implementation, it is essential to reassign the parent's child pointers (e.g., root.left = delete(...)) to reflect the changes in the subtree.

Up Next:
Now that you can create, search, insert into, and delete from a BST, our next step is to learn about tree traversal algorithms. These are standardized ways to visit every node in a tree. We will cover pre-order, in-order, and post-order traversals. You've already seen a practical use for in-order traversal (printing elements in sorted order), and in the next lesson, you'll learn how to implement it and its counterparts formally.