BST in C#

Binary Search Tree in C#

using System;

public class Node
{
    public int data;
    public Node left;
    public Node right;

    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
}

public class BST
{
    Node root, newNode;
    int n,tNode;
    bool flag;
    public BST()
    {
        root = null;
        newNode = null;
        tNode=0;
    }

    public void Add(Node current)
    {
        if (current.data > newNode.data)
        {
            if (current.left != null)
            {
                current = current.left;
                Add(current);
            }
            else
                current.left = newNode;
        }
        else if (current.data <= newNode.data)
        {
            if (current.right != null)
            {
                current = current.right;
                Add(current);
            }
            else
                current.right = newNode;
        }
    }

    public void Insert()
    {
        Console.Write("Enter a number : ");
        n = Convert.ToInt32(Console.ReadLine());
        newNode = new Node(n);
        if (root == null)
            root = newNode;
        else
        {
            Add(root);
        }
    }

    public void PostOrder(Node root)
    {
 
        if (root.left != null)
            PostOrder(root.left);
        if (root.right != null)
            PostOrder(root.right);
        Console.Write(root.data + "\t");
    }
   
    public void countNode(Node root)
    {
        if (root.left != null)
            countNode(root.left);
        if (root.right != null)
            countNode(root.right);
        tNode++;
    }
   
    public void leaf()
    {
       if(root!=null)
       {
         leafCount(root);
         Console.Write("Total leaf node is:"+tNode);
       }
       else
       Console.Write("List is empty");
    }
   
    public void leafCount(Node root)
    {
       if(root.left!=null)
         leafCount(root.left);
       if(root.right!=null)
         leafCount(root.right);
       if(root.right==null && root.left==null)
       {
         tNode++;
       } 
    }
   
     public void interNode()
     {
       if(root!=null)
       {
         internalNodes(root);
         Console.Write("Total internal nodes:"+tNode);
       }
       else
       Console.WriteLine("List is empty");
     }
     public void internalNodes(Node root)
     {
        if(root.left!=null)
         internalNodes(root.left);
        if(root.right!=null)
         internalNodes(root.right);
        if(!(root.right==null && root.left==null))
        {
           tNode++;
        }
     }
    
     public void search()
    {
       if(root!=null)
       {
         flag=false;
         Console.Write("Enter the value for searching:");
         n=Convert.ToInt32(Console.ReadLine());
         searchElement(root);
         if(flag)
         {
           Console.WriteLine("Element found");
         }
         else
         Console.Write("Element not found");
       }
       else
       Console.WriteLine("List is empty");
    }
    public void searchElement(Node root)
    {
      
        if (root.left != null)
           searchElement(root.left);
        if (root.right != null)
            searchElement(root.right);
            if(root.data==n)
            {
                flag=true;
            }   
    }
   
    public void previous()
    {
     
      if(root!=null)
      {
        Console.Write("Element for dislay:");
        n=Convert.ToInt32(Console.ReadLine());
        searchPrevious(root);
        if(flag==true)
        {
          Console.Write("Element found");
          Console.Write("\nCurrent Element is : "+cur.data);         
          Console.Write("\nPrevious Element is : "+pre.data);
        }
        else
        Console.Write("Element not found");
      }
      else
      Console.WriteLine("List is empty");
    }
   
    Node cur=null,pre=null;
    public void searchPrevious(Node root)
    {
     
      if(root.left!=null)
      {
         pre=root;
         cur=root.left;
       if(root.data==n)
       {
         flag=true;
       }
         searchPrevious(root.left);
      }
      if(root.right!=null)
      {
         pre=root;
         cur=root.right;
      if(root.data==n)
      {
         flag=true;
      }
         searchPrevious(root.right);
      }
   
    }
   
   
    public void totalNodes()
    {
       if(root!=null)
       {
         flag=false;
         Console.Write("Enter the value for counting nodes:");
         n=Convert.ToInt32(Console.ReadLine());
         Node s=nodeTotal(root);
         if(flag && s!=null)
         {
           tNode=0;        
                       countNode(s);      
           Console.Write("Total nodes="+(tNode-1));
         }
         else
         Console.WriteLine("Element not found");
       }
       else
       Console.WriteLine("List is empty");
    }
   
    Node found=null;
    public Node nodeTotal(Node root)
    { 
        if (root.left != null)
           nodeTotal(root.left);
        if (root.right != null)
            nodeTotal(root.right);
            if(root.data==n)
            {
                flag=true;
                found=root;
                return found;
            }   
            else
              return found;
    }
   
    public void count()
    {
      if(root!=null)
        countNode(root);
      Console.Write("\ntotal nodes ="+tNode); 
    }
   
    public void leftCount()
    {
       if(root!=null)
       {
           tNode=0;
           countLeft(root.left);
           Console.WriteLine("Total nodes in the left of root : "+tNode);
       }
       else       
       {
         Console.WriteLine("List is empty");
       }
    }
    public void countLeft(Node root)
    {
       if(root.left!=null)
          countLeft(root.left);
       if(root.right!=null)
          countLeft(root.right);
       tNode++;
    }
    public void rightCount()
    {
       if(root!=null)
       {
           tNode=0;
           countRight(root.right);
           Console.WriteLine("Total nodes in the right of root : "+tNode);
       }
       else       
       {
         Console.WriteLine("List is empty");
       }
    }
    public void countRight(Node root)
    {
       if(root.left!=null)
          countLeft(root.left);
       if(root.right!=null)
          countLeft(root.right);
       tNode++;
    }
   
    public void PreOrder(Node root)
    {
        Console.Write(root.data + "\t");
        if (root.left != null)
            PreOrder(root.left);
        if (root.right != null)
            PreOrder(root.right);
    }

    public void InOrder(Node root)
    {
        if (root.left != null)
            InOrder(root.left);
        Console.Write(root.data+"\t");
        if (root.right != null)
            InOrder(root.right);
    }
    public void Display()
    {
        if (root != null)
        {

            Console.WriteLine("\nPreOrder Traversal");
            PreOrder(root);
            Console.WriteLine("\nInOrder Traversal");
            InOrder(root);
            Console.WriteLine("\nPostOrder Traversal");
            PostOrder(root);
        }
        else
            Console.WriteLine("BST is empty");
    }
    public static void Main(String[] args)
    {
        BST b = new BST();
        int k;
        char ch;
        do
        {
            Console.Write("=======Menu=====");
            Console.Write("\n1.Insert\n2.display\n3.Count Node\n4.Search\n5.Total Left Nodes Of Root"
            +"\n6.Total right Nodes Of Root\n7.Total Nodes Of Any Element\n8.Total Leaf Node\n9.Internal Nodes\n10.Show Previous element\n11.Exit\n");
            Console.Write("Choose your option:");
            k = Convert.ToInt32(Console.ReadLine());
            if (k == 1)
                b.Insert();
            else if (k == 2)
                b.Display();
            else if(k==3)
              b.count();
            else if(k==4)
              b.search();
            else if(k==5)
            b.leftCount() ;
            else if (k==6)
            b.rightCount();
            else if(k==7)
            b.totalNodes();
            else if(k==8)
            b.leaf();
            else if(k==9)
            b.interNode(); 
            else if(k==10)
            b.previous();
            else
                break;
            Console.Write("\nDo u want to continue(y/n):");
            ch = Convert.ToChar(Console.ReadLine());
            Console.Clear();
        } while (ch == 'y' || ch == 'Y');
    }
}

output