Write a program to demonstrate deletion node from Binary Search Tree

Solution

using System;

namespace SerachTreeOpearations
{
    class Program
    {
        static void Main()
        {
            var bt = new BinarySearchTree<int>();
            bt.Add(50);
            bt.Add(30);
            bt.Add(70);
            bt.Add(60);
            bt.Add(10);
            bt.Add(90);

            Console.WriteLine("Binary search tree ");
            bt.PrintTree(bt.Root);

            bt.DeleteNode(bt.Root, 70);
            Console.WriteLine("\n After deleting Binary search tree");
            bt.PrintTree(bt.Root);
            Console.ReadLine();
        }
    }

    public class BinarySearchTree<T> where T : IComparable<T>
    {
        public Node<T> Root;

        public BinarySearchTree()
        {
            Root = null;
        }

        public void Add(T data)
        {
            var newNode = new Node<T>(data);
            if (Root == null)
            {
                Root = newNode;
                return;
            }

            var current = Root;

            while (true)
            {
                var parent = current;
                if (data.CompareTo(current.Data) < 0)
                {
                    current = current.Left;
                    if (current != null) continue;
                    parent.Left = newNode;
                    return;
                }

                current = current.Right;
                if (current != null) continue;
                parent.Right = newNode;
                return;
            }
        }

        public Node<T> MinNode(Node<T> root)
        {
            return root.Left != null ? MinNode(root.Left) : root;
        }

        public Node<T> DeleteNode(Node<T> node, T value)
        {
            if (node == null)
            {
                return null;
            }

            if (value.CompareTo(node.Data) < 0)
            {
                node.Left = DeleteNode(node.Left, value);
            }
            else if (value.CompareTo(node.Data) > 0)
            {
                node.Right = DeleteNode(node.Right, value);
            }
            else
            {
                if (node.Left == null && node.Right == null)
                    node = null;

                else if (node.Left == null)
                {
                    node = node.Right;
                }
                else if (node.Right == null)
                {
                    node = node.Left;
                }
                else
                {
                    var temp = MinNode(node.Right);
                    node.Data = temp.Data;
                    node.Right = DeleteNode(node.Right, temp.Data);
                }
            }
            return node;
        }

        public void PrintTree(Node<T> node)
        {
            if (Root == null)
            {
                Console.WriteLine("Tree is empty");
                return;
            }

            if (node.Left != null)
                PrintTree(node.Left);
            Console.Write(node.Data + "\t");
            if (node.Right != null)
                PrintTree(node.Right);
        }
    }

    public class Node<T>
    {
        public T Data;
        public Node<T> Left;
        public Node<T> Right;

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