using System;

public class Program

{

    public static void Main()

    {

        BinaryTree bt = new BinaryTree();

        Tree root = bt.Insert(null,100);

        root = bt.Insert(root,50);

        root = bt.Insert(root,70);

        root = bt.Insert(root,200);

        root = bt.Insert(root,170);

        root = bt.Insert(root,150);

        root = bt.Insert(root,25);

        root = bt.Insert(root,45);

        root = bt.Insert(root,10);

        Console.WriteLine("------------------Pre Order -------------------");

        bt.PrintPreOrder(root);

​

        Console.WriteLine("------------------In Order -------------------");

        bt.PrintInOrder(root);

        Console.WriteLine("------------------Post Order -------------------");

        bt.PrintPostOrder(root);

        int val = 175;

        bool found = bt.Find(root,val);

        if ( found )

        {

            Console.WriteLine("------------------Node [{0}] found  -------------------", val);

        }

        else

        {

            Console.WriteLine("------------------Node [{0}] NOT found  -------------------", val);

        }

            Console.WriteLine("------------------Depth of tree is  [{0}]  -------------------", bt.FindDepth(root));

    }

    public class BinaryTree

    {

        public void PrintPreOrder(Tree root)

        {

            if ( root == null ) return;

            Console.WriteLine(root.data);

            PrintPreOrder(root.left);

            PrintPreOrder(root.right);

        }

        public void PrintInOrder(Tree root)

        {

            if ( root == null ) return;

            PrintInOrder(root.left);

            Console.WriteLine(root.data);

            PrintInOrder(root.right);

        }

        public void PrintPostOrder(Tree root)

        {

            if ( root == null ) return;

            PrintPostOrder(root.left);

            PrintPostOrder(root.right);

            Console.WriteLine(root.data);

        }

        public Tree Insert(Tree root, int value)

        {

            if ( root == null ) 

                return new Tree { data = value, left = null, right = null };

            if ( value < root.data )

            {

                root.left = Insert(root.left, value);

            }

            else

            {

                root.right = Insert(root.right, value);

            }

            return root;

        }

        public bool Find(Tree root,int value)

        {

            if ( root == null ) return false;

            if ( root.data == value ) return true;

            if ( value < root.data )

                return Find(root.left,value);

            else

                return Find(root.right,value);

        }

        public int FindDepth(Tree root)

        {

            if ( root== null ) return 0;

            return 1+FindDepth(root.left) + FindDepth(root.right) ;

        }

    }

    public class Tree 

    {

        public int data;

        public Tree left;

        public Tree right;

    };

}