using System;   

public class Node

{

    public int data;

    public Node left,right;

}

public class Tree

{

    public Node head=new Node();

    public Tree()

    {       

        head=null;

    }

    public void NodeInsertion(Node parent,Node child)

    {

        if(parent.data>=child.data&&parent.left==null)

        parent.left=child;

        else if(parent.data<child.data&&parent.right==null)

        parent.right=child;

        else

        {

            if(parent.data>=child.data)

            NodeInsertion(parent.left,child);

            else

            NodeInsertion(parent.right,child);

        }

    }

    public Node TreeConstruction(int input)

    {

        Node temp=new Node();

        temp.data=input;

        temp.left=null;

        temp.right=null;

        if(head==null)

        head=temp;

        else

        NodeInsertion(head,temp);

        return head;

    }

    public void AscendingOrder(Node temp,int key,ref int flag)

    {

         if (temp!= null)

         {

             AscendingOrder(temp.left,key,ref flag);

             if(temp.data==key)

                flag++; 

             Console.Write(temp.data +" ");

             AscendingOrder(temp.right,key,ref flag);

         }      

    }

    public void DescendingOrder(Node temp)

    {

        if(temp!=null)

        {

             DescendingOrder(temp.right);   

            Console.Write(temp.data +" ");          

            DescendingOrder(temp.left);

        }

    }               

    public void Operations()

    {

        int input;

        Node current=new Node();

        do

        {

            Console.WriteLine("Enter node value:");

            input=Convert.ToInt32(Console.ReadLine());

            if(input!=-1)

            current=this.TreeConstruction(input);

        }while(input!=-1);

        int key,flag=-1;

        Console.WriteLine("enter element to search:");

        key=Convert.ToInt32(Console.ReadLine());

        Console.WriteLine("Elements in Ascending order are:");

        this.AscendingOrder(current,key,ref flag);

        Console.WriteLine("\nElements in Descending order are:");

        this.DescendingOrder(current);

        if(flag==-1)

            Console.WriteLine("\nRegarding Searching:\nSearch is UnSuccessful");

        else

            Console.WriteLine("\nRegarding Searching:\nSearch is Successful");      

    }       

}

public class Program

{

    public static void Main()

    {

        Tree obj=new Tree();

        obj.Operations();

    }

}