using System;

public class TreeNode

{

    int data;

    TreeNode parent;

    TreeNode left;

    TreeNode right;

    public TreeNode(int data)

    {

        this.data = data;

        parent = left = right = null;

    }

​

    public void setData(int data)

    {

        this.data = data;

    }

​

    public void setLeft(TreeNode node)

    {

        left = node;

    }

​

    public void setRight(TreeNode node)

    {

        right = node;

    }

​

    public void setParent(TreeNode node)

    {

        parent = node;

    }

​

    public int getData()

    {

        return data;

    }

​

    public TreeNode getLeft()

    {

        return left;

    }

​

    public TreeNode getRight()

    {

        return right;

    }

​

    public TreeNode getParent()

    {

        return parent;

    }

}

​

​

​

//Inserting a node into a BST:

public static void insert(TreeNode node)

{

    TreeNode x, y;

          // root is a global variable and is the root of the tree

    x = y = root; // Assume root is initialized to null

    while (x != null)

    {

        if (x.getData() > node.getData())

        {

            y = x;

            x = x.getLeft();

        }

        else

        {

            y = x;

            x = x.getRight();

        }

    }

    // y will be the parent of node

    if (y == null) 

    {

        root = node;

        return;

    }

    if (y.getData() > node.getData())

        y.setLeft(node);

    else

        y.setRight(node);

    node.setParent(y);

}

​

​

//Deleting a node from a BST:

​

public static void delete(TreeNode node)

{

    // Case 1: node does not have a child, just delete it

    if (node.getLeft() == null && node.getRight() == null)

    {

        if (node.getParent() != null && node.getParent().getLeft() == node)

            node.setLeft(null);

        else if (node.getParent() != null && node.getParent().getRight() == node)

            node.setRight(null);            

    }

    // Case 2: node has only one child, splice the child with its parent

    else if (node.getLeft() == null || node.getRight() == null)

    {

        if (node.getParent() != null)

        {

            TreeNode x = node.getLeft() == null ? node.getRight() : node.getLeft();

            if (node.getParent().getLeft() == node)

                node.getParent().setLeft(x);

            else

                node.getParent().setRight(x);

        }            

    }

    // Case 3: node has both children, set the successor of the node to its parent

    else

    {

        TreeNode x = findSuccessor(node); // x will have at most one child

        // Instead of deleting we can just copy the successor's data over to the node to be deleted

        node.setData(x.getData());

        // Now delete the successor and set its child (if any) to its parent

        TreeNode nodeChild = x.getLeft() == null ? x.getRight() : x.getLeft();

        if (x.getLeft() != null)

        {

            if (x.getParent().getLeft() == x)

                x.getParent().setLeft(nodeChild);

            else

                x.getParent().setRight(nodeChild);

        }

        else

        {

            if (x.getParent().getLeft() == x)

                x.getParent().setLeft(nodeChild);

            else

                x.getParent().setRight(nodeChild);

        }

    }

}

​

//Finding the minimum value in the tree:

​

public TreeNode findMinimum(TreeNode root)

{

    if (root == null)

        return null;

    if (root.getLeft() != null)

        return findMinimum(root.getLeft());

    return root;

}

​

//Finding the maximum value in the tree:

public static TreeNode findMaximum(TreeNode root)

{

    if (root == null)

        return null;

    if (root.getRight() != null)

        return findMaximum(root.getRight());

    return root;

}

​

//Finding the successor node of a given node:

public static TreeNode findSuccessor(TreeNode node)

{

    if (node == null)

        return null;

    if (node.getRight() != null)

        return findMinimum(node.getRight());

    TreeNode y = node.getParent();

    TreeNode x = node;

    while (y != null && x == y.getRight())

    {

        x = y;

        y = y.getParent();

    }

​

    return y;

}

​

//Finding the predecessor node of a given node:

public static TreeNode findPredecessor(TreeNode node)

{

    if (node == null)

        return null;

    if (node.getLeft() != null)

        return findMaximum(node.getLeft());

    TreeNode y = node.getParent();

    TreeNode x = node;

    while (y != null && x == y.getLeft())

    {

        x = y;

        y = y.getParent();

    }

​

    return y;

}

​

​

​

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

}