C# program to delete nodes from binary search tree

Here's an example of a C# program that implements deleting nodes from a binary search tree:

using System;

class Node
{
    public int Data;
    public Node Left;
    public Node Right;

    public Node(int data)
    {
        Data = data;
        Left = null;
        Right = null;
    }
}

class BinarySearchTree
{
    private Node root;

    public void Insert(int data)
    {
        root = InsertRecursive(root, data);
    }

    private Node InsertRecursive(Node current, int data)
    {
        if (current == null)
        {
            return new Node(data);
        }

        if (data < current.Data)
        {
            current.Left = InsertRecursive(current.Left, data);
        }
        else if (data > current.Data)
        {
            current.Right = InsertRecursive(current.Right, data);
        }

        return current;
    }

    public void Delete(int data)
    {
        root = DeleteRecursive(root, data);
    }

    private Node DeleteRecursive(Node current, int data)
    {
        if (current == null)
        {
            return null;
        }

        if (data < current.Data)
        {
            current.Left = DeleteRecursive(current.Left, data);
        }
        else if (data > current.Data)
        {
            current.Right = DeleteRecursive(current.Right, data);
        }
        else
        {
            // Case 1: No child or only one child
            if (current.Left == null)
            {
                return current.Right;
            }
            else if (current.Right == null)
            {
                return current.Left;
            }

            // Case 2: Two children
            current.Data = FindMinValue(current.Right);
            current.Right = DeleteRecursive(current.Right, current.Data);
        }

        return current;
    }

    private int FindMinValue(Node current)
    {
        int minValue = current.Data;
        while (current.Left != null)
        {
            minValue = current.Left.Data;
            current = current.Left;
        }
        return minValue;
    }

    public void InorderTraversal()
    {
        InorderTraversalRecursive(root);
        Console.WriteLine();
    }

    private void InorderTraversalRecursive(Node current)
    {
        if (current != null)
        {
            InorderTraversalRecursive(current.Left);
            Console.Write(current.Data + " ");
            InorderTraversalRecursive(current.Right);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree bst = new BinarySearchTree();

        // Inserting elements into the binary search tree
        bst.Insert(50);
        bst.Insert(30);
        bst.Insert(20);
        bst.Insert(40);
        bst.Insert(70);
        bst.Insert(60);
        bst.Insert(80);

        // Performing inorder traversal of the binary search tree
        Console.WriteLine("Inorder Traversal of the Binary Search Tree:");
        bst.InorderTraversal();

        // Deleting elements from the binary search tree
        int deleteValue = 30;
        bst.Delete(deleteValue);
        Console.WriteLine($"Deleted {deleteValue} from the binary search tree.");

        // Performing inorder traversal after deletion
        Console.WriteLine("Inorder Traversal of the Binary Search Tree:");
        bst.InorderTraversal();
    }
}

This program creates a binary search tree class ('BinarySearchTree') that contains a private 'Node' class. The 'Node' class represents each node in the binary search tree and holds the data and references to the left and right child nodes.

The 'BinarySearchTree' class provides two methods: 'Insert' and 'Delete'. The 'Insert' method inserts a new node with the given data into the binary search tree. The 'Delete' method deletes a node with the given data from the binary search tree. The 'Delete' method handles three cases: 1) when the node to be deleted has no child or only one child, and 2) when the node to be deleted has two children. In the case of two children, it finds the minimum value in the right subtree and replaces the node's data with that value. It then recursively deletes the node with the minimum value from the right subtree.

In the 'Main' method, we create an instance of 'BinarySearchTree', insert elements into the binary search tree using the Insert method, and then perform an inorder traversal of the tree using the 'InorderTraversal' method. Next, we delete a node with the value 30 using the 'Delete' method and print a message indicating the deleted value. Finally, we perform an inorder traversal of the tree again to see the updated tree after deletion.

Inorder Traversal of the Binary Search Tree:
20 30 40 50 60 70 80
Deleted 30 from the binary search tree.
Inorder Traversal of the Binary Search Tree:
20 40 50 60 70 80

This demonstrates the implementation of deleting nodes from a binary search tree in C#. The program successfully deletes the node with the value 30 from the binary search tree and updates the tree accordingly.