using System;

​

public abstract class Tree<T> where T:IComparable {

}

​

public class Empty<T> : Tree<T> where T:IComparable {

}

​

public class Node<T> : Tree<T> where T:IComparable {

    public T Data {get; private set; }

    public Tree<T> Left {get;private set;}

    public Tree<T> Right {get;private set;}

    public Node(T v, Tree<T> l, Tree<T> r) {

        Data = v;

        Left = l;

        Right = r;

    }

}

​

public class BinaryTree<T> where T:IComparable {

    public Tree<T> Insert(T v, Tree<T> tree) {

        switch (tree) {

            case Empty<T> dummy:

                return new Node<T>(v, new Empty<T>(), new Empty<T>());

            case Node<T> node:

                T x = node.Data;

                Tree<T> l = node.Left;

                Tree<T> r = node.Right;

                if (v.CompareTo(x) == 0) {

                    return tree;

                } else {

                    if (v.CompareTo(x) < 0) {

                        return new Node<T>(v, Insert(x, l), r);

                    } else {

                        return new Node<T>(x, l, Insert(v, r));

                    }

                }

        }

        throw new Exception("Stop doing dumb things");

    }

}

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        BinaryTree<int> t = new BinaryTree<int>();

        t.Insert(10, new Empty<int>());

        Console.WriteLine(t);

    }

}