GenericBinaryTree.java

public static class GenericBinaryTree {

        public static void main(String[] args) {
           Tree t = new EmptyBST();
           t = t.add(4);

           t = t.add(3);
           t = t.add(5);

           System.out.println(t.member(0));

        }

        public interface Tree<D extends Comparable> {
            public boolean isEmpty();

            public boolean member(D elt);

            public int cardinality();

            public NonEmtyBST<D> add(D elt);
        }


        public static class EmptyBST<D extends Comparable> implements Tree<D> {

            @Override
            public boolean isEmpty() {
                return true;
            }

            @Override
            public boolean member(D elt) {
                return false;
            }

            @Override
            public int cardinality() {
                return 0;
            }

            @Override
            public NonEmtyBST<D> add(D elt) {
                return new NonEmtyBST<D>(elt);
            }
        }


        public static class NonEmptyBST<D extends Comparable> implements Tree<D> {
            D data;
            Tree<D> left;
            Tree<D> right;

            public NonEmtyBST(D elt) {
                data = elt;
                left = new EmptyBST<D>();
                right = new EmptyBST<D>();
            }

            public NonEmtyBST(D elt, Tree<D> leftTree, Tree<D> rightTree) {
                data = elt;
                left = leftTree;
                right = rightTree;
            }

            @Override
            public boolean isEmpty() {
                return false;
            }

            @Override
            public boolean member(D elt) {
                if (data == elt) {
                    return true;
                } else {
                    if (elt.compareTo(data) < 0) {
                        return left.member(elt);
                    } else {
                        return right.member(elt);
                    }
                }
            }

            @Override
            public int cardinality() {
                return 1 + left.cardinality() + right.cardinality();
            }

            @Override
            public NonEmptyBST<D> add(D elt) {
                if (data == elt) {
                    return this;
                } else {
                    if (elt.compareTo(data) < 0) {
                        return new NonEmptyBST<>(data, left.add(elt), right);
                    } else {
                        return new NonEmptyBST<D>(data, left, right.add(elt));
                    }
                }
            }
        }
    }