Deletion in BST in Data Structures Theory - Full Explanation

Introduction

Imagine you have a sorted collection of items arranged in a tree shape, and you want to remove one item without messing up the order. Deletion in a Binary Search Tree (BST) solves this problem by carefully removing the item while keeping the tree organized.

Explanation

Deleting a Leaf Node

When the node to delete has no children, it is called a leaf node. Removing it is simple because it does not affect other nodes. You just remove the node and update its parent's pointer to null.

Deleting a leaf node is straightforward since it has no children to worry about.

Deleting a Node with One Child

If the node to delete has only one child, you remove the node and connect its parent directly to that child. This keeps the tree connected and maintains the BST order.

For nodes with one child, link the parent to the child to keep the tree intact.

Deleting a Node with Two Children

This is the trickiest case. You find the node's successor (the smallest node in its right subtree) or predecessor (the largest node in its left subtree). Replace the node's value with the successor's or predecessor's value, then delete that successor or predecessor node, which will have at most one child.

Replace the node with its successor or predecessor to maintain BST order before deleting.

Real World Analogy

Imagine a bookshelf arranged by book titles in alphabetical order. Removing a book with no neighbors is easy—just take it out. If a book has one neighbor, you slide the neighbor over to fill the gap. If a book is between two others, you replace it with the next book in order and then remove that next book from its original spot.

Deleting a Leaf Node → Taking out a book at the end of the shelf with no books next to it

Deleting a Node with One Child → Sliding a neighboring book over to fill the empty spot

Deleting a Node with Two Children → Replacing a book with the next book in alphabetical order, then removing that next book from its place

Diagram

Diagram

       ┌─────┐
       │ 50  │
       └──┬──┘
          │
    ┌─────┴─────┐
    │           │
 ┌──┴──┐     ┌──┴──┐
 │ 30  │     │ 70  │
 └──┬──┘     └──┬──┘
    │           │
  ┌─┴─┐       ┌─┴─┐
  │ 20 │       │ 80 │
  └────┘       └────┘

Deleting node 30 (with one child 20):

       ┌─────┐
       │ 50  │
       └──┬──┘
          │
    ┌─────┴─────┐
    │           │
  ┌─┴─┐       ┌─┴─┐
  │ 20 │       │ 70 │
  └────┘       └──┬──┘
                   │
                 ┌─┴─┐
                 │ 80 │
                 └────┘

This diagram shows a BST before and after deleting a node with one child, illustrating how the child replaces the deleted node.

Key Facts

Leaf Node Deletion → Removing a node with no children by simply disconnecting it from its parent.

Single Child Deletion → Removing a node with one child by linking its parent directly to that child.

Two Children Deletion → Replacing the node with its in-order successor or predecessor before deleting.

In-order Successor → The smallest node in the right subtree of a node.

In-order Predecessor → The largest node in the left subtree of a node.

Code Example

Data Structures Theory

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

def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete_node(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = min_value_node(root.right)
        root.key = temp.key
        root.right = delete_node(root.right, temp.key)
    return root

def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

# Build tree
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.right.right = Node(80)

print("Before deletion:", inorder(root))
root = delete_node(root, 30)
print("After deleting 30:", inorder(root))

Common Confusions

Thinking you can just remove any node without adjusting the tree.

Thinking you can just remove any node without adjusting the tree. Removing a node without reconnecting its children breaks the BST structure and order.

Always using the in-order successor for replacement.

Always using the in-order successor for replacement. You can use either the in-order successor or predecessor; both maintain BST properties.

Summary

Deleting nodes in a BST requires careful handling to keep the tree ordered and connected.

Leaf nodes are easiest to delete, while nodes with two children need replacement by successor or predecessor.

Understanding these cases helps maintain efficient search and update operations in BSTs.