23tree.cs

using System;
using System.Linq;

public abstract class Tree<T>
    where T : IComparable<T>
{
    private static readonly Tree<T> LeafInstance = new Leaf();

    protected class Notification
    {
        public bool Success { get; private set; }
        public Tree<T> Tree { get; private set; }
        public T Value { get; private set; }
        public Tree<T> Left { get; private set; }
        public Tree<T> Right { get; private set; }

        private Notification(bool success, Tree<T> tree, T value, Tree<T> left, Tree<T> right)
        {
            Success = success;
            Tree = tree;
            Value = value;
            Left = left;
            Right = right;
        }

        public static Notification Ok(Tree<T> tree)
        {
            return new Notification(true, tree, default(T), null, null);
        }

        public static Notification Transform(T value, Tree<T> left, Tree<T> right)
        {
            return new Notification(false, null, value, left, right);
        }
    }

    public class Leaf : Tree<T>
    {
        protected override Notification InsertCore(T value)
        {
            return Notification.Transform(value, LeafInstance, LeafInstance);
        }
    }

    public class Node2 :Tree<T>
    {
        public T Value { get; private set; }
        public Tree<T> Left { get; private set; }
        public Tree<T> Right { get; private set; }

        public Node2(T value, Tree<T> left, Tree<T> right)
        {
            Value = value;
            Left = left;
            Right = right;
        }

        protected override Notification InsertCore(T value)
        {
            if (value.CompareTo(Value) < 0)
            {
                var result = Left.InsertCore(value);
                return result.Success 
                    ? Notification.Ok(new Node2(Value, result.Tree, Right)) 
                    : Notification.Ok(new Node3(result.Value, Value, result.Left, result.Right, Right));
            }
            else
            {
                var result = Right.InsertCore(value);
                return result.Success
                           ? Notification.Ok(new Node2(Value, Left, result.Tree))
                           : Notification.Ok(new Node3(Value, result.Value, Left, result.Left, result.Right));
            }
        }
    }

    public class Node3 : Tree<T>
    {
        public T Value1 { get; private set; }
        public T Value2 { get; private set; }
        public Tree<T> Left { get; private set; }
        public Tree<T> Middle { get; private set; }
        public Tree<T> Right { get; private set; }

        public Node3(T value1, T value2, Tree<T> left, Tree<T> middle, Tree<T> right)
        {
            Value1 = value1;
            Value2 = value2;
            Left = left;
            Middle = middle;
            Right = right;
        }

        protected override Notification InsertCore(T value)
        {
            if (value.CompareTo(Value1) < 0)
            {
                var result = Left.InsertCore(value);
                return result.Success
                           ? Notification.Ok(new Node3(Value1, Value2, result.Tree, Middle, Right))
                           : Notification.Transform(Value1, new Node2(result.Value, result.Left, result.Right),
                                                    new Node2(Value2, Middle, Right));

            }
            else if (value.CompareTo(Value2) < 0)
            {
                var result = Middle.InsertCore(value);
                return result.Success
                           ? Notification.Ok(new Node3(Value1, Value2, Left, result.Tree, Right))
                           : Notification.Transform(result.Value, new Node2(Value1, Left, result.Left),
                                                    new Node2(Value2, result.Right, Right));
            }
            else
            {
                var result = Right.InsertCore(value);
                return result.Success
                           ? Notification.Ok(new Node3(Value1, Value2, Left, Middle, result.Tree))
                           : Notification.Transform(Value2, new Node2(Value1, Left, Middle),
                                                    new Node2(result.Value, result.Left, result.Right));
            }

            
        }
    }


    protected abstract Notification InsertCore(T value);

    public static Tree<T> New()
    {
        return LeafInstance;
    }

    public Tree<T> Insert(T value)
    {
        var insertResult = InsertCore(value);
        return insertResult.Success 
            ? insertResult.Tree 
            : new Node2(insertResult.Value, insertResult.Left, insertResult.Right);
    }
}


public static class Program
{
    public static void Main(string[] args)
    {
        var tree = Enumerable.Range(1, 10).Aggregate(Tree<int>.New(), (current, c) => current.Insert(c));
    }
}