Deleting Nodes In Binary Search Tree

Deleting nodes in a binary search tree (BST) is the process of removing a value from a BST while preserving the tree’s most important property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. Now, this operation may sound simple, but deletion is more complex than insertion because removing a node can accidentally break the ordering rule. Understanding how to delete nodes correctly is essential for maintaining efficient search, insertion, and removal operations in balanced or unbalanced binary search trees Simple, but easy to overlook..

Easier said than done, but still worth knowing.

Introduction to Binary Search Trees

A binary search tree is a hierarchical data structure made up of nodes. Each node contains:

• A key or value
• A reference to a left child
• A reference to a right child

The binary search tree property states:

• The left subtree of a node contains only values less than the node’s value.
• The right subtree contains only values greater than the node’s value.

Because of this structure, searching for a value can be efficient. Starting from the root, the algorithm compares the target value with the current node and moves left or right accordingly That alone is useful..

To give you an idea, if we want to delete a value from a BST, we first search for it using the same logic as normal search. Once the node is found, the method used to delete it depends on how many children that node has The details matter here..

Why Deleting a Node Is More Complicated Than Inserting

Inserting a new node into a binary search tree is usually straightforward. You compare values and place the new node in the correct empty position.

Deleting is different because removing a node can disconnect part of the tree. If the node has children, simply removing it would leave those children without their parent, which may violate the BST structure.

Here's one way to look at it: consider this BST:

        50
       /  \
     30    70
    / \    /
   20 40  60

If we delete 50, we cannot just remove it and leave 30 and 70 disconnected. The resulting tree must still satisfy the BST property. One valid deletion result is:

        60
       /  \
     30    70
    / \
   20 40

Here, 60 replaces 50, and the BST property remains valid.

Important BST Deletion Cases

When deleting a node from a binary search tree, there are three main cases:

1. The node has no children.
2. The node has one child.
3. The node has two children.

Each case requires a slightly different approach Practical, not theoretical..

Case 1: Deleting a Leaf Node

A leaf node is a node with no left or right children Worth keeping that in mind..

Example:

        50
       /  \
     30    70
    / \
   20 40

If we delete 40, it is a leaf node. Since it has no children, we can remove it directly by updating its parent’s right pointer to null.

The tree becomes:

        50
       /  \
     30    70
    /
   20

This is the easiest deletion case because no replacement value is needed The details matter here..

Steps for Deleting a Leaf Node

To delete a leaf node:

1. Search for the node.
2. Find its parent.
3. Determine whether it is the left or right child.
4. Set the parent’s corresponding child reference to null.

Case 2: Deleting a Node with One Child

A node with one child can also be removed without much difficulty. Instead of deleting the node itself, we connect its parent directly to its only child.

Consider this tree:

        50
       /  \
     30    70
    /
   20

If we delete 30, it has one child, 20. We remove 30 and connect 50 directly to 20.

The result is:

        50
       /  \
     20    70

This preserves the BST property because 20 is still less than 50.

Steps for Deleting a Node with One Child

To delete a node with one child:

1. Find the node to delete.
2. Identify its only child.
3. Connect the node’s parent to the child.
4. If the node is the root, make the child the new root.

This case is common in BST deletion because many nodes have only one subtree Still holds up..

Case 3: Deleting a Node with Two Children

The most complicated case is deleting a node with two children. This happens when the node has both a left and a right subtree.

Example:

        50
       /  \
     30    70
    / \    /
   20 40  60

If we delete 50, we cannot simply remove it because both 30 and 70 are roots of important subtrees. To maintain the BST property, we need to replace the node’s value with another value from the tree.

There are two standard choices:

• The inorder successor
• The inorder predecessor

Inorder Successor

The inorder successor of a node is the smallest value in its right subtree.

To give you an idea, in this tree:

        50
       /  \
     30    70
    / \    /
   20 40  60

The inorder successor of 50 is 60, because 60 is the smallest value in the right subtree of 50 No workaround needed..

To delete a node using its inorder successor:

1. Find the smallest node in the right subtree.
2. Copy that node’s value into the node being deleted.
3. Delete the successor node from its original position.

After deleting 50 using 60, the tree becomes:

        60
       /  \
     30    70
    / \
   20 40

The BST property is preserved Worth keeping that in mind..

Inorder Predecessor

The inorder predecessor of a node is the largest value in its left subtree.

As an example, in this tree:

        50
       /  \
     30    70
    / \    /
   20 40  60

The inorder predecessor of 50 is 40, because 40 is the largest value in the left subtree of 50 That's the part that actually makes a difference. Practical, not theoretical..

Using the predecessor, we copy 40 into 50 and delete the original 40 node.

The result is: