using System;

​

public class Node

{

    public int key;

    public Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

public class BinarySearchTree{

Node root;

public BinarySearchTree()

{

    root = null;

}

public void insert(int key)

{

    root = insertRec(root, key);

}

Node insertRec(Node root, int key)

{

    if (root == null)

    {

        root = new Node(key);

        return root;

    }

    if (key < root.key)

        root.left = insertRec(root.left, key);

    else if (key > root.key)

        root.right = insertRec(root.right, key);

    return root;

}

public void inorder()

{

    inorderRec(root);

}

void inorderRec(Node root)

{

    if (root != null)

    {

        inorderRec(root.left);

        Console.WriteLine(root.key);

        inorderRec(root.right);

    }

}

public void postorder()

{

    postorderRec(root);

}

void postorderRec(Node root)

{

    if (root != null)

    {

        postorderRec(root.left);

        postorderRec(root.right);

        Console.WriteLine(root.key);

    }

}

public void preorder()

{

    preorderRec(root);

}

void preorderRec(Node root)

{

    if (root != null)

    {

        Console.WriteLine(root.key);

        preorderRec(root.left);

        preorderRec(root.right);

    }

}

    public void deleteKey(int key) { root = deleteRec(root, key); }

    Node deleteRec(Node root, int key)

    {

        if (root == null)

            return root;

        if (key < root.key)

            root.left = deleteRec(root.left, key);

        else if (key > root.key)

            root.right = deleteRec(root.right, key);

        else {

            if (root.left == null)

                return root.right;

            else if (root.right == null)

                return root.left;

            root.key = minValue(root.right);

            root.right = deleteRec(root.right, root.key);

        }

        return root;

    }

    int minValue(Node root)

    {

        int minv = root.key;

        while (root.left != null) {

            minv = root.left.key;

            root = root.left;

        }

        return minv;

    }

 }

// Driver Code

public class Program{

    public static void Main(String[] args)

{

    BinarySearchTree tree = new BinarySearchTree();

    /* Let us create following BST

          4

       /     \

      2      20

     /  \       \

   1     3      25 

               /

              23

   */

    tree.insert(4);

    tree.insert(2);

    tree.insert(1);

    tree.insert(3);

    tree.insert(20);

    tree.insert(25);

    tree.insert(23);

    tree.preorder();

    Console.WriteLine();

    tree.deleteKey(4);

    tree.preorder();

}

}

​

​

​