Delete a Node in a BST Explained: Tracing Deleting 3 then 5

Imagine you are handed the binary search tree represented by the sequence 5, 3, 6, 2, 4, null, 7. Here, 5 is the root, with a left subtree rooted at 3 (having children 2 and 4) and a right subtree rooted at 6 (having a right child 7). Everything is orderly: left descendants are smaller, right descendants are larger. But what happens when you decide to delete node 3, and then root node 5?

If you simply sever a node from its parent like a leaf on a linked list, you risk stranding entire subtrees or violating the fundamental BST invariant where every left child is less than its parent and every right child is greater. Deleting a leaf like 2 or 7 is trivial, but deleting an internal node with one or two children creates structural gaps. You cannot just remove node 3 and leave its children 2 and 4 floating in the memory void, nor can you arbitrarily promote 4 to take 3's place without checking whether the rest of the tree still respects the ordering rules.

This is why BST deletion demands a systematic strategy: you are not just updating a single pointer, you are surgically repairing a hierarchical network. Throughout this guide, we will track the exact sequence of deletions on our initial BST: first deleting 3 (a node with two children), and then deleting root 5 (also with two children), observing every intermediate pointer mutation along the way.

# Given BST: 5, 3, 6, 2, 4, null, 7
# Goal: Delete 3, then delete 5.
# Question: Explain in 1-2 sentences why deleting node 3 is structurally harder than deleting leaf node 7.

When we perform structural surgery on a Binary Search Tree, we cannot simply snip a pointer without violating the core invariant: for any node, all left descendants are smaller, and all right descendants are larger. In our working example tree 5 with left subtree 3 (having children 2 and 4) and right subtree 6 (having right child 7), deleting a node falls into one of three distinct topological cases.

First, consider deleting a leaf node (such as 2 or 7). Because it has no descendants, we only need to sever its parent's pointer by replacing it with null, keeping the rest of the tree intact.

Second, consider deleting a node with exactly one child. The sole subtree can safely slide up to take the deleted node's place in the parent's pointer field, bypassing the removed node entirely.

Third, consider deleting a node with two children, which is what happens when we delete 3 or root 5 in our working example. Because both left and right subtrees are populated, we cannot replace 3 with a single child without leaving an orphaned branch. Instead, we find the in-order successor (the minimum value in the right subtree) or the in-order predecessor, copy its value into the target node, and then recursively delete that successor from its original position.

5
/ \
3 6
/ \ \
2 4 7

When we delete 3, it has two children (2 and 4). Its right subtree starts at 4, which has no left child, making 4 the in-order successor. Copying 4 into node 3's position and removing the old 4 leaf preserves the BST property without breaking the remaining hierarchy.

Try this: Given the working tree: root 5, left 3 (children 2, 4), right 6 (child 7). Explain which of the three structural cases applies when deleting node 2 versus deleting node 3.

Let us trace the exact sequence for our working example: a BST constructed from $5,3,6,2,4,\text{null},7$.

5
/ \
3 6
/ \ \
2 4 7

Given: We want to delete key 3. Node 3 has two children (2 and 4).

Steps:
1. Locate node 3 starting from root 5 (go left). Confirm it has both a left child (2) and a right child (4).
2. Find the in-order successor in the right subtree of 3. The right subtree root is 4, and it has no left child. Thus, the successor value is 4.
3. Copy the successor value (4) into node 3. Node 3 now holds 4, temporarily creating a duplicate 4 in its right child.
4. Recursively delete the successor node (4) from the right subtree. Since 4 is a leaf, it is removed by updating its parent's right pointer to null.

5
/ \
4 6
/ \
2 7

Given: From the original BST structure (or the updated one, but let us stick to the primary prompt sequence: deleting 3 then deleting root 5 from that modified state or original state), let us trace deleting root 5.

Steps:
1. Locate root 5. It has two children (4 on the left, 6 on the right after our deletion of 3).
2. Find the in-order successor in the right subtree (rooted at 6). The minimum value in the right subtree is 6 (since 6 has no left child, only right child 7).
3. Copy successor value 6 into the root position. The root now holds 6.
4. Recursively delete the successor node (6) from its original position. Since 6 has a right child (7), deleting 6 falls under the single-child case: replace 6 with its right child 7.

6
/ \
4 7
/
2

This yields our final structural state: 6, 4, 7, 2. Notice how every deletion preserves the BST invariant ($left<parent<right$).

Now it is time to test your mental model against our locked working example. Recall our initial BST: root 5, with left subtree 3 (having children 2 and 4) and right subtree 6 (having right child 7). In the previous phase, we walked through deleting node 3 (which had two children) and then deleting the root node 5.

To ensure you can execute these structural surgeries on your own, answer the following scenario-based task. Do not skip the intermediate states; trace how pointers shift when the successor is pulled upward.

Practice Question:
Given our starting BST structure (root 5, left 3 with 2 and 4, right 6 with 7), write out the exact sequence of steps and the final tree structure when you perform only the deletion of node 3 first, and then immediately attempt to delete the new root. What is the value of the successor chosen when removing node 3, and where does it end up?

Try this: BST initial state: 5 -> left: 3 (2, 4), right: 6 (null, 7).
Task: Trace deletion of 3, then deletion of 5.

Now that you have traced deleting node 3 and root 5 from our original BST 5, 3, 6, 2, 4, null, 7, let us test your transfer of these rules on a structurally altered tree. Suppose your starting tree is modified to have no right subtree on node 5, or you need to delete a node whose right subtree is entirely single-valued.

Consider a BST with keys 8, 3, 10, 1, 6, null, 14. You are asked to delete root 8, and then immediately delete node 3.

When deleting root 8, it possesses both a left child (3) and a right child (10). Following the two-child deletion pattern established in our working example, you locate the in-order successor in the right subtree — which is 10 (or its leftmost descendant). Since 10 has a right child (14) but no left child, replacing root 8's value with 10 and restructuring the right child requires grafting 14 directly into 10's former position.

Next, you delete node 3, which has two children (1 and 6). Its in-order successor is 6 (or the minimum of its right subtree). Replacing 3 with 6 and removing the original 6 node completes the transformation without violating the BST invariant.

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

# Given BST: 8, 3, 10, 1, 6, None, 14
root = Node(8,
            Node(3, Node(1), Node(6)),
            Node(10, None, Node(14))
)

# Question: Write out or trace the resulting tree structure after deleting 8, then deleting 3.