Binary Search Tree - Linked List Implementation

Node Class
----------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class Node
     {
          public int item;
          public Node parent;
          public Node left;
          public Node right;

          public Node()
          {
          }

          public Node(int item)
          {
               this.item = item;
          }

          public int Item
          {
               get { return item; }
          }

     }
}


BST Class
------------------------------------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class BST
     {
         

          private Node root;

          public BST()
          {
               root = null;
          }

          public Node Root
          {
               get { return root; }
          }

          public void insert(int item)
          {
               Node x, y;
               Node z = new Node(item);
               y = null;
               x = root;
               while (x != null)
               {
                    y = x;
                    if (z.item < x.item)
                         x = x.left;
                    else
                         x = x.right;
               }
               z.parent = y;
               if (y == null)
                    root = z;
               else
               {
                    if (z.item < y.item)
                         y.left = z;
                    else
                         y.right = z;
               }
          }

          public void preorder(Node root)
          {
               if (root != null)
               {
                    Console.Write("{0} ", root.item);
                    preorder(root.left);
                    preorder(root.right);
               }
          }

          public void inorder(Node root)
          {
               if (root != null)
               {
                    inorder(root.left);
                    Console.Write("{0} ", root.item);
                    inorder(root.right);
               }
          }

          public void postorder(Node root)
          {
               if (root != null)
               {
                    postorder(root.left);
                    postorder(root.right);
                    Console.Write("{0} ", root.item);
               }
          }

          public Node minimum(Node root)
          {
               Node ptr = root;

               while (ptr.left != null)
               {
                    ptr = ptr.left;
               }
               return ptr;
          }

          public Node maximum(Node root)
          {
               Node ptr = root;

               while (ptr.right != null)
               {
                    ptr = ptr.right;
               }
               return ptr;
          }

          public Node successor(Node ptr)
          {
              Node succ;
               if (ptr.right != null)
                   return minimum(ptr.right);
               succ = ptr.parent;
               while (succ != null && ptr == succ.right)
               {
                    ptr = succ;
                    succ = succ.parent;
               }
               return succ;
          }

          public Node search(Node root, int item)
          {
               while (root != null && item != root.item)
               {
                    if (item < root.item)
                         root = root.left;
                    else
                         root = root.right;
               }
               return root;
          }

          public void  delete(Node root,  Node z)
          {
               Node x, y;

              if ( z.left == null || z.right == null)
                   y = z;
              else
                   y = successor(z);
              if (y.left != null)
                   x = y.left;
              else
                   x = y.right;
              if ( x != null)
                   x.parent = y.parent;
              if (y.parent == null)
                   root = x;
              else {
                   if ( y == y.parent.left)
                        y.parent.left = x;
                  else
                       y.parent.right = x;
              }

               if ( y != z) {
                    z.item = y.item;
               }
          }

          public bool isEmpty()
          {
               return root == null;
          }
     }
}

Driver Program Using BST Class
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
using System;

namespace BST_Linked_List_Implementation
{
     class Program
     {
          static void Main(string[] args)
          {
               BST bst = new BST();
              
               bst.insert(20);
               bst.insert(10);
               bst.insert(30);
               bst.insert(5);
               bst.insert(15);
               bst.insert(25);
               bst.insert(35);

               bst.preorder(bst.Root);
               Console.WriteLine();
               bst.inorder(bst.Root);
               Console.WriteLine();
               bst.postorder(bst.Root);
               Console.WriteLine();
               Console.WriteLine("Minimum = {0}", bst.minimum(bst.Root).Item.ToString());
               Console.WriteLine("Maximum = {0}", bst.maximum(bst.Root).Item.ToString());
               Node ptr = bst.search(bst.Root, 20);
               if (ptr != null)
               {
                    bst.delete(bst.Root, ptr);
               }
               bst.inorder(bst.Root);
               Console.WriteLine();
              

               Console.ReadKey();

          }
     }
}