(Naïve) implementation of immutable double-ended queues (deques) based on balanced binary trees.

Deque+Empty.cs

using System;

partial class Deque<T>
{
    private sealed class Empty<T> : IDeque<T>
    {
        public IDeque<T> PushFront(T value)
        {
            return new Deque<T>(value, Deque<T>.Empty, Deque<T>.Empty);
        }
    
        T IDeque<T>.PeekFront()
        {
            throw new InvalidOperationException();
        }
    
        IDeque<T> IDeque<T>.PopFront()
        {
            return this;
        }
    
        int IDeque<T>.Height { get { return 0; } }
    }
}

Deque.cs

using System;

public sealed partial class Deque<T> : IDeque<T>
{
    public Deque(T value, IDeque<T> left, IDeque<T> right)
    {
        this.Value = value;
        this.Left = left;
        this.Right = right;
    }

    public T Value { get; private set; }
    public IDeque<T> Left  { get; private set; }
    public IDeque<T> Right { get; private set; }

    int IDeque<T>.Height { get { return 1 + Math.Max(this.Left.Height, this.Right.Height); } }

    public bool IsLeftmost
    {
        get { return this.Left is Empty<T>; }
    }

    public IDeque<T> PushFront(T value)
    {
        if (this.IsLeftmost)
        {
            return new Deque<T>(this.Value,
                                new Deque<T>(value, Deque<T>.Empty, Deque<T>.Empty),
                                this.Right).TryRebalance();
        }
        else
        {
            return new Deque<T>(this.Value,
                                this.Left.PushFront(value),
                                this.Right).TryRebalance();
        }
        // NB: ideally, the node creation and re-balancing would be done in one single step!
    }

    public T PeekFront()
    {
        if (this.IsLeftmost)
        {
            return this.Value;
        }
        else
        {
            return this.Left.PeekFront();
        }
    }

    public IDeque<T> PopFront()
    {
        if (this.IsLeftmost)
        {
            return this.Right;
        }
        else
        {
            return new Deque<T>(this.Value,
                                this.Left.PopFront(),
                                this.Right).TryRebalance();
        }
        // NB: ideally, the node creation and re-balancing would be done in one single step!
    }

    private IDeque<T> TryRebalance()
    {
        var balance = this.Right.Height - this.Left.Height;
        if (balance > 1)
        {
            return this.TryRotateLeft();
        }
        else if (balance < -1)
        {
            return this.TryRotateRight();
        }
        else
        {
            return this;
        }
    }

    private IDeque<T> TryRotateLeft()
    {
        if (this.Right is Deque<T>)
        {
            var right = this.Right as Deque<T>;
            return new Deque<T>(right.Value,
                                new Deque<T>(this.Value, this.Left, right.Left),
                                right.Right);
        }
        else
        {
            return this;
        }
    }

    private IDeque<T> TryRotateRight()
    {
        if (this.Left is Deque<T>)
        {
            var left = this.Left as Deque<T>;
            return new Deque<T>(left.Value,
                                left.Left,
                                new Deque<T>(this.Value, left.Right, this.Right));
        }
        else
        {
            return this;
        }
    }

    public static readonly IDeque<T> Empty = new Empty<T>();
}

IDeque.cs

public interface IDeque<T>
{
    IDeque<T> PushFront(T value);
    T PeekFront();
    IDeque<T> PopFront();
    int Height { get; }
}

This gist is referred in the Stack Overflow question, Implement an immutable deque as a balanced binary tree?