DualBranch.java

final class DualBranch<T extends Comparable<T>> extends NonEmptyTree<T> {
    private final ImmutableBinaryTree<T> leftChild;
    private final ImmutableBinaryTree<T> rightChild;

    public DualBranch(final T value, final ImmutableBinaryTree<T> left, final ImmutableBinaryTree<T> right) {
        super(value);
        leftChild = left;
        rightChild = right;
    }

    @Override
    protected ImmutableBinaryTree<T> getLeft() {
        return leftChild;
    }

    @Override
    protected ImmutableBinaryTree<T> getRight() {
        return rightChild;
    }

}

EmptyTree.java

final class EmptyTree<T extends Comparable<T>> extends ImmutableBinaryTree<T> {
    private EmptyTree() { }

    @Override
    public ImmutableBinaryTree<T> add(final T element) {
        return new Leaf<T>(element);
    }

    @Override
    public ImmutableBinaryTree<T> remove(final T element) {
        return this;
    }

    @Override
    public boolean contains(final T element) {
        return false;
    }

    @Override
    public List<T> toList() {
        return Collections.emptyList();
    }

    @Override
    protected ImmutableBinaryTree<T> addAll(final ImmutableBinaryTree<T> tree) {
        return tree;
    }

    @SuppressWarnings("rawtypes")
    private static final EmptyTree INSTANCE = new EmptyTree();

    @SuppressWarnings("unchecked")
    static <U extends Comparable<U>> ImmutableBinaryTree<U> instance() {
        return INSTANCE;
    }
}

ImmutableBinaryTree.java

public abstract class ImmutableBinaryTree<T extends Comparable<T>> implements ImmutableSet<T> {

    @Override
    public abstract ImmutableBinaryTree<T> add(T element);

    @Override
    public abstract ImmutableBinaryTree<T> remove(T element);

    protected abstract ImmutableBinaryTree<T> addAll(ImmutableBinaryTree<T> tree);

    public static <U extends Comparable<U>> ImmutableBinaryTree<U> create() {
        return EmptyTree.instance();
    };

    public static <U extends Comparable<U>> ImmutableBinaryTree<U> create(final U... elems) {
        ImmutableBinaryTree<U> tree = create();
        for (U elem : elems) {
            tree = tree.add(elem);
        }
        return tree;
    };
}

Leaf.java

final class Leaf<T extends Comparable<T>> extends NonEmptyTree<T> {
    Leaf(final T val) {
        super(val);
    }

    @Override
    protected ImmutableBinaryTree<T> getLeft() {
        return EmptyTree.instance();
    }

    @Override
    protected ImmutableBinaryTree<T> getRight() {
        return EmptyTree.instance();
    }
}

LeftBranch.java

final class LeftBranch<T extends Comparable<T>> extends SingleBranch<T> {
    LeftBranch(final T val, final ImmutableBinaryTree<T> child) {
        super(val, child);
    }

    @Override
    protected ImmutableBinaryTree<T> getLeft() {
        return getChild();
    }

    @Override
    protected ImmutableBinaryTree<T> getRight() {
        return EmptyTree.instance();
    }
}

NonEmptyTree.java

abstract class NonEmptyTree<T extends Comparable<T>> extends ImmutableBinaryTree<T> {

    private final T value;

    public NonEmptyTree(final T val) {
        value = val;
    }

    protected abstract ImmutableBinaryTree<T> getLeft();

    protected abstract ImmutableBinaryTree<T> getRight();

    @Override
    public final ImmutableBinaryTree<T> add(final T element) {
        if (value.equals(element)) {
            return this;
        }
        return addAll(new Leaf<T>(element));
    }

    @Override
    public final ImmutableBinaryTree<T> remove(final T element) {
        if (value.equals(element)) {
            return getLeft().addAll(getRight());
        }
        if (value.compareTo(element) > 0) {
            return replaceChildren(getLeft().remove(element), getRight());
        }
        return replaceChildren(getLeft(), getRight().remove(element));
    }

    @Override
    protected ImmutableBinaryTree<T> addAll(final ImmutableBinaryTree<T> tree) {
        ImmutableBinaryTree<T> emptyTree = EmptyTree.instance();
        if (tree == emptyTree) {
            return this;
        }
        NonEmptyTree<T> nTree = (NonEmptyTree<T>) tree;
        if (value.equals(nTree.value)) {
            return replaceChildren(getLeft().addAll(nTree.getLeft()), getRight().addAll(nTree.getRight()));
        }
        if (value.compareTo(nTree.value) > 0) {
            return replaceChildren(getLeft().addAll(tree), getRight());
        }
        return replaceChildren(getLeft(), getRight().addAll(tree));
    }

    private ImmutableBinaryTree<T>
            replaceChildren(final ImmutableBinaryTree<T> leftBranch, final ImmutableBinaryTree<T> rightBranch) {
        if (leftBranch == getLeft() && rightBranch == getRight()) {
            return this;
        }
        ImmutableBinaryTree<T> emptyTree = EmptyTree.instance();
        if (leftBranch == emptyTree && rightBranch == emptyTree) {
            return new Leaf<T>(value);
        }
        if (leftBranch == emptyTree) {
            return new RightBranch<T>(value, rightBranch);
        }
        if (rightBranch == emptyTree) {
            return new LeftBranch<T>(value, leftBranch);
        }
        return new DualBranch<T>(value, leftBranch, rightBranch);
    }

    @Override
    public final boolean contains(final T element) {
        if (value.equals(element)) {
            return true;
        }
        if (value.compareTo(element) > 0) {
            return getLeft().contains(element);
        }
        return getRight().contains(element);
    }

    @Override
    public final List<T> toList() {
        List<T> list = new LinkedList<T>();
        list.addAll(getLeft().toList());
        list.add(value);
        list.addAll(getRight().toList());
        return list;
    }
}

RightBranch.java

final class RightBranch<T extends Comparable<T>> extends SingleBranch<T> {
    RightBranch(final T val, final ImmutableBinaryTree<T> child) {
        super(val, child);
    }

    @Override
    protected ImmutableBinaryTree<T> getLeft() {
        return EmptyTree.instance();
    }

    @Override
    protected ImmutableBinaryTree<T> getRight() {
        return getChild();
    }

}

SingleBranch.java

abstract class SingleBranch<T extends Comparable<T>> extends NonEmptyTree<T> {
    private final ImmutableBinaryTree<T> child;

    SingleBranch(final T val, final ImmutableBinaryTree<T> childTree) {
        super(val);
        child = childTree;
    }

    protected final ImmutableBinaryTree<T> getChild() {
        return child;
    }
}