using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        BinarySearchTree<int> tree = new BinarySearchTree<int>();

        tree.Insert(2);

        tree.Insert(1);

        tree.Insert(3);

        Console.WriteLine(tree.IsValidBinarySearchTreeRecursive(tree.root).ToString()); // this is supposed to return true when tested against the simple tree above

    }

}

​

public class Node<T> where T : IComparable

{

    public Node<T> left;

    public Node<T> right;

    public T data;

    public Node(T data)

    {

        this.left = null;

        this.right = null;

        this.data = data;

    }

}

​

public class BinarySearchTree<T> where T : IComparable

{

    public Node<T> root;

    public BinarySearchTree()

    {

        this.root = null;

    }

    public bool Insert(T data)

    {

        Node<T> before = null;

        Node<T> after = this.root;

        while(after != null)

        {

            before = after;

            if(data.CompareTo(after.data) < 0)

                after = after.left;

            else if(data.CompareTo(after.data) > 0)

                after = after.right;

            else

                return false;

        }

        Node<T> newNode = new Node<T>(data);

        if (this.root == null)

        {

            this.root = newNode;

        }

        else

        {

            if(data.CompareTo(before.data) < 0)

                before.left = newNode;

            else

                before.right = newNode;

        }

​

        return true;

    }

    private bool _HelperForIsValidBinarySearchTreeRecursive(Node<T> node, T lower, T upper)

    {

        if (node == null)

            return true;

​

        T val = node.data;

        Type nodeType = typeof(T);

​

        if(nodeType.IsNumeric())

        {

            if(val.CompareTo(lower) <= 0)

                return false;

            if(val.CompareTo(upper) >= 0)

                return false;

        }

        else

        {

            if(lower != null && val.CompareTo(lower) <= 0)

                return false;

            if(upper != null && val.CompareTo(upper) >= 0)

                return false;

        }

​

        if(!_HelperForIsValidBinarySearchTreeRecursive(node.right, val, upper))

            return false;

        if(!_HelperForIsValidBinarySearchTreeRecursive(node.left, lower, val))

            return false;

        return true;

    }

    public bool IsValidBinarySearchTreeRecursive(Node<T> root)

    {

        Type nodeType = typeof(T);

        if(nodeType.IsNumeric())

            return _HelperForIsValidBinarySearchTreeRecursive(root, root.data, root.data);

        return _HelperForIsValidBinarySearchTreeRecursive(root, default(T), default(T));

    }

}

​

public static class StaticUtilities

{

    private static readonly HashSet<Type> NumericTypes = new HashSet<Type>

    {

        typeof(int),  typeof(double),  typeof(decimal),

        typeof(long), typeof(short),   typeof(sbyte),

        typeof(byte), typeof(ulong),   typeof(ushort),  

        typeof(uint), typeof(float)

    };

    public static bool IsNumeric(this Type myType)

    {

        return NumericTypes.Contains(Nullable.GetUnderlyingType(myType) ?? myType);

    }

}