TDD Immutable Stack After Roy Osherove Master Class Yes I know the Size property is in 0(n) time currently.

tddstack.cs

namespace ImmutableDatastructures
{

    public interface IImmutableStack<T>{
        IImmutableStack<T> Push(T value);
        IImmutableStack<T> Pop();
        T Head{get;}
        IImmutableStack<T> Tail{ get;}
        int Size{get;}
        bool IsEmpty();
    }

  public class ImmutableStack<T> : IImmutableStack<T>
	{

        private class EmptyImmutableStack : IImmutableStack<T>
        {
            public IImmutableStack<T> Push(T value)
            {
                return new ImmutableStack<T>{
                    Head = value,
                    Tail = this
                };
            }

            public IImmutableStack<T> Pop()
            {
                throw new System.InvalidOperationException("Cannot call pop on an empty stack.");
            }

            public bool IsEmpty()
            {
                return true;
            }

            public T Head
            {
                get
                {
                    throw new System.InvalidOperationException("Cannot get the head on an empty stack.");
                }
            }

            public IImmutableStack<T> Tail
            {
                get
                {
                    throw new System.InvalidOperationException("Cannot get the tail on an empty stack.");
                }
            }

            public int Size
            {
                get
                {
                    return 0;
                }
            }

        }

        public static IImmutableStack<T> Empty()
        {
            return new EmptyImmutableStack();
        }

        private ImmutableStack(){

        }

        public IImmutableStack<T> Push(T value)
        {
            return new ImmutableStack<T>{
                Head = value,
                Tail = this
            };
        }

        public IImmutableStack<T> Pop()
        {
            return Tail;
        }

        public T Head
        {
            get;
            protected set;
        }

        public IImmutableStack<T> Tail
        {
            get;
            protected set;
        }

        public int Size
        {
            get{
                var otherSize = (Tail == null) ? 0 : Tail.Size;
                return 1 + otherSize;
            }
        }

        public bool IsEmpty()
        {
            return false;
        }
    }
}

using NUnit.Framework;
using System;

namespace ImmutableDatastructures
{
  [TestFixture()]
	public class ImmutableStackTests
	{
		[Test]
		public void EmptyStack_AsDefaultStack_ShouldItIsEmpty()
		{
            IImmutableStack<int> stack = GetEmptyStack();

			Assert.IsTrue(stack.IsEmpty());

		}

		[Test]
		public void Push_OnAnEmptyStack_ShouldReturnAStackWithASingleElementAsTheHeadButHasNoTail()
		{
            IImmutableStack<int> stack = GetEmptyStack();

            IImmutableStack<int> newStack = stack.Push(1);

			Assert.AreEqual(1,newStack.Head);

		}
		
		[Test]
		public void Push_OnAnEmptyStack_ShouldReturnAStackWithASingleElement()
		{
            IImmutableStack<int> stack = GetEmptyStack();
			
            IImmutableStack<int> newStack = stack.Push(1);
			
			Assert.AreEqual(1,newStack.Size);
			
		}
		
		[Test]
		public void Push_OnAStackWithASingleElementAdded_ShouldReturnANewStackWithATailContainingThePreviousValue(){
            IImmutableStack<int> stack = GetEmptyStack();
			
            IImmutableStack<int> newStack = stack.Push(1);
			
            IImmutableStack<int> anotherStack = newStack.Push(2);
			
			Assert.AreEqual(1, anotherStack.Tail.Head);
		}

        [Test]
        public void Push_OnAStackWithASingleElementAdded_TheSizeShouldBeTwo(){
            IImmutableStack<int> stack = GetEmptyStack();
            
            IImmutableStack<int> newStack = stack.Push(1);
            
            IImmutableStack<int> anotherStack = newStack.Push(2);
            
            Assert.AreEqual(2, anotherStack.Size);
        }

        [Test]
        public void Head_OnAnEmptyStack_ShouldThrowAnInvalidOperationExceptionIndicatingTheHeadIsNotSetOnAnEmptyStack(){
            IImmutableStack<int> stack = GetEmptyStack();
            
            Assert.Throws<InvalidOperationException>( () => {
                var head = stack.Head;
            });
        }

        [Test]
        public void Tail_OnAnEmptyStack_ShouldThrowAnInvalidOperationExceptionIndicatingTheTailIsNotSetOnAnEmptyStack(){
            IImmutableStack<int> stack = GetEmptyStack();
            
            Assert.Throws<InvalidOperationException>( () => {
                var tail = stack.Tail;
            });
        }

        [Test]
        public void Pop_EmptyStack_ItShouldThrowAnInvalidOperationExceptionIndicatingTheStackIsEmpty(){
            IImmutableStack<int> stack = GetEmptyStack();

            Assert.Throws<InvalidOperationException>( () => {
                var nextTopOfStack = stack.Pop();
            });
        }

        [Test]
        public void Pop_AStackWithASingleElementAdded_ItShouldReturnTheEmptyStack(){
            IImmutableStack<int> stack = GetEmptyStack();
            IImmutableStack<int> newStack = stack.Push(1);
            
            Assert.IsTrue(newStack.Pop().IsEmpty());
        }

        static IImmutableStack<int> GetEmptyStack()
		{
			return ImmutableStack<int>.Empty();
		}

	}
}