Binary Search Tree (BST) Node Deleteion Algorythm in C#

What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a binary tree data structure where each node has a value, and all values in the left subtree are less than the node's value, while all values in the right subtree are greater.
BSTs allow efficient searching, insertion, and deletion operations in O(log n) average time complexity for balanced trees.

Why does Deletion Matter?

Deletion is an essential operation for maintaining the integrity and performance of a BST over time. Depending on the node type, deletion involves different strategies:

Case 1: Deleting a leaf node (no children), simply remove it.
Case 2: Deleting a node with one child, replace it with its child.
Case 3: Deleting a node with two children, replace it with its in-order successor (smallest node in right subtree).

Handling these cases properly keeps the BST structure correct after each operation.

Real-World Applications of BST Concepts

While pure BSTs are often academic examples, their concepts, efficient ordered search, insertions, and deletions, are the foundation of real-world production systems:

Database Indexes (e.g., PostgreSQL, MySQL) use B-Trees, which generalize BST principles for efficient lookup and updates.
Filesystems (e.g., NTFS, ext4) organize files and directories using B+-Trees derived from BST logic.
Memory Management systems use tree structures to allocate and deallocate memory blocks dynamically.
In-memory data Stores like Redis implement sorted sets and fast lookups with tree-based structures.
Gaming and Graphics Engines utilize spatial partitioning trees to optimize collision detection and rendering.

Understanding how to properly modify tree structures, including safe deletions, is critical for building resilient, high-performance software systems.

BST Deletion Algorithm Explained

How Deletion Works in a BST

Find the Node to delete by traversing the tree.
Handle One of Three Cases:
- Leaf Node (no children): Remove it directly.
- Node with One Child: Replace the node with its child.
- Node with Two Children
  - Find the in-order successor (smallest value in the right subtree).
  - Replace the node's value with the successor’s value.
  - Delete the successor node.

By maintaining these steps, the BST remains valid and ordered after deletion.

Full C# Code

public class BinaryTreeNode(int value)
{
    public int Value { get; set; } = value;
    public BinaryTreeNode? Left { get; set; }
    public BinaryTreeNode? Right { get; set; }
}

public static class BinaryTreeOperations
{
    public static BinaryTreeNode? DeleteFromBst(BinaryTreeNode? root, List<int> values)
    {
        if (values == null || values.Count == 0)
            return root;

        foreach (var v in values)
        {
            root = Delete(root, v);
        }
        return root;
    }

    public static BinaryTreeNode? Delete(BinaryTreeNode root, int value)
    {
        if (root == null)
            return null;

        BinaryTreeNode? parent = null;
        BinaryTreeNode? current = root;

        // Search for the node
        while (current != null && current.Value != value)
        {
            parent = current;
            current = value < current.Value ? current.Left : current.Right;
        }

        if (current == null)
            return root; // Value not found

        // Case 1: Leaf node
        if (current.Left == null && current.Right == null)
        {
            if (parent == null)
                return null; // Root was the only node
            if (parent.Left == current)
                parent.Left = null;
            else
                parent.Right = null;
        }
        // Case 2: Node with one child
        else if (current.Left == null || current.Right == null)
        {
            var child = current.Left ?? current.Right;
            if (parent == null)
                return child; // Root node replaced
            if (parent.Left == current)
                parent.Left = child;
            else
                parent.Right = child;
        }
        // Case 3: Node with two children
        else
        {
            var successorParent = current;
            var successor = current.Right;

            while (successor.Left != null)
            {
                successorParent = successor;
                successor = successor.Left;
            }

            current.Value = successor.Value;

            if (successorParent.Left == successor)
                successorParent.Left = successor.Right;
            else
                successorParent.Right = successor.Right;
        }

        return root;
    }
}

Unit Testing with xUnit and FluentAssertions

using System.Collections.Generic;
using FluentAssertions;
using Xunit;

public class BinaryTreeOperationsTests
{
    [Fact]
    public void DeleteFromBst_ShouldDeleteLeafNode()
    {
        var root = new BinaryTreeNode(5)
        {
            Left = new BinaryTreeNode(3),
            Right = new BinaryTreeNode(7)
        };

        root = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 3 });

        root.Should().NotBeNull();
        root!.Value.Should().Be(5);
        root.Left.Should().BeNull();
        root.Right.Should().NotBeNull();
        root.Right!.Value.Should().Be(7);
    }

    [Fact]
    public void DeleteFromBst_ShouldDeleteNodeWithOneChild()
    {
        var root = new BinaryTreeNode(5)
        {
            Left = new BinaryTreeNode(3),
            Right = new BinaryTreeNode(7)
            {
                Left = new BinaryTreeNode(6)
            }
        };

        root = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 7 });

        root.Should().NotBeNull();
        root!.Value.Should().Be(5);
        root.Right.Should().NotBeNull();
        root.Right!.Value.Should().Be(6);
        root.Right.Left.Should().BeNull();
        root.Right.Right.Should().BeNull();
    }

    [Fact]
    public void DeleteFromBst_ShouldDeleteNodeWithTwoChildren()
    {
        var root = new BinaryTreeNode(5)
        {
            Left = new BinaryTreeNode(3),
            Right = new BinaryTreeNode(8)
            {
                Left = new BinaryTreeNode(6),
                Right = new BinaryTreeNode(9)
            }
        };

        root = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 8 });

        root.Should().NotBeNull();
        root!.Value.Should().Be(5);
        root.Right.Should().NotBeNull();
        root.Right!.Value.Should().Be(9); // Successor replacement
    }

    [Fact]
    public void DeleteFromBst_ShouldReturnNull_WhenDeletingRootLeaf()
    {
        var root = new BinaryTreeNode(1);

        root = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 1 });

        root.Should().BeNull();
    }

    [Fact]
    public void DeleteFromBst_ShouldNotFail_WhenValueNotFound()
    {
        var root = new BinaryTreeNode(5)
        {
            Left = new BinaryTreeNode(3),
            Right = new BinaryTreeNode(7)
        };

        var result = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 10 });

        result.Should().NotBeNull();
        result!.Value.Should().Be(5);
        result.Left.Should().NotBeNull();
        result.Left!.Value.Should().Be(3);
        result.Right.Should().NotBeNull();
        result.Right!.Value.Should().Be(7);
    }
}

Usage Example

Here’s a small tree, deleting values, and printing in-order traversal to verify the result:

public static void Main()
{
    var root = new BinaryTreeNode(5)
    {
        Left = new BinaryTreeNode(3),
        Right = new BinaryTreeNode(8)
        {
            Left = new BinaryTreeNode(6),
            Right = new BinaryTreeNode(9)
        }
    };

    Console.WriteLine("Original tree (in-order):");
    PrintInOrder(root);
    Console.WriteLine();

    root = BinaryTreeOperations.DeleteFromBst(root, new List<int> { 8 });

    Console.WriteLine("Tree after deleting 8 (in-order):");
    PrintInOrder(root);
    Console.WriteLine();
}

public static void PrintInOrder(BinaryTreeNode? node)
{
    if (node == null) return;
    PrintInOrder(node.Left);
    Console.Write($"{node.Value} ");
    PrintInOrder(node.Right);
}

Output

This validates that the BST structure remains correct after deletion.

Conclusion

Proper deletion in a Binary Search Tree is critical for maintaining a valid, efficient search structure. This article demonstrated how to handle all deletion cases safely, write production-quality C# code, and verify correctness with unit tests using FluentAssertions.

Mastering dynamic tree operations is not just theoretical. It helps you grow as a Software Engineer and understand the real-world challenges in database systems, search engines, file systems, and memory management.