using System;

using System.Collections;

using System.Collections.Generic;

public class Program

{

    public static BinarySearchTree<int> MyTree = new BinarySearchTree<int>();

    public static void Main()

    {

        MyTree.Add(9);

        MyTree.Add(2);

        MyTree.Add(5);

        MyTree.Add(1);

        MyTree.Add(4);

        MyTree.Add(3);

        MyTree.PrintNodes();

    }

}

​

public class BinarySearchTree<T> where T : IComparable {

    public Node<T> Root { get; private set; }

    public int Length {  get; private set; }

    public void Add(T data) {

        if(Root == null) {

            Root = new Node<T>() {

                Data = data

            };

            return;

        }       

        Add(data, Root);        

    }

    public void PrintNodes() {

        PrintNodes(Root);       

    }

    private void PrintNodes(Node<T> current) {

        if(current.Left != null) PrintNodes(current.Left);

        Console.Write(current.Data);

        if(current.Right !=null) PrintNodes(current.Right);     

    }

    public void Add(T data,Node<T> current){

        if(current.Data.CompareTo(data) > 0) {

            if(current.Left == null) {

                current.Left = new Node<T>() {

                    Data = data

                };

            }

            else {

                Add(data,current.Left);

            }

        }

        else {

            if(current.Right == null) {

                current.Right = new Node<T>(){

                    Data = data

                };

            }

            else {

                Add(data,current.Right);

            }

        }       

    }

    public bool IsValidTree(Node<T> current){

​

        Queue<Node<T>> queue = new Queue<Node<T>>();

        queue.Enqueue(current);

        while(queue.Count > 0) {

            var dequeued = queue.Dequeue();

            if(dequeued.Left != null) {

                if(dequeued.Left.Data.CompareTo(dequeued.Data) > 0) return false;

                queue.Enqueue(dequeued.Left);

            }

            if(dequeued.Right != null) {

                if(dequeued.Right.Data.CompareTo(dequeued.Data) < 0) return false;

                queue.Enqueue(dequeued.Right);

            }           

        }       

        return true;

    }

}

​

public class Node<T> where T : IComparable {

    public Node<T> Left { get; set; }

    public Node<T> Right { get; set; }

    public T Data { get; set; }

}