I'm trying to write a size() method for a polymorphic binary search tree. I.e. A BST that has classes EmptyTree and NonEmptyTree that both implement a "tree" interface. EmptyTree is being used to represent an empty tree or subtree instead of null (like in a regular BST)

public interface Tree<K extends Comparable<K>, V> {
    public int size();
    public NonEmptyTree<K, V> add(K key, V value);

    //bunch of other methods
}

I've made both EmptyTree and NonEmptyTree implement the size() method from the Tree interface like so:

public int size() { //in EmptyTree class
   return 0;
}

public int size() { //in NonEmptyTree class
   return 1 + left.size() + right.size();
}

However, when I try to run this in a test:

Tree<Integer, String> treeThree = EmptyTree.getInstance(); //EmptyTree is a singleton class
   treeThree = treeThree.add(3, "3"); 
   treeThree = treeThree.add(2, "2"); 
   treeThree = treeThree.add(1, "1"); 
   treeThree = treeThree.add(4, "4");
   assertEquals(4, treeThree.size());

It says that the size of treeThree is 3, rather than 4 like it should be.

It works just fine for these ones though:

        Tree<Integer, String> empty = EmptyTree.getInstance();
        assertEquals(0, empty.size());

        Tree<Integer, String> treeOne = EmptyTree.getInstance();
        treeOne = treeOne.add(2, "2"); treeOne = treeOne.add(1, "1"); treeOne = treeOne.add(3, "3");
        assertEquals(3, treeOne.size());

        Tree<Integer, String> treeTwo = EmptyTree.getInstance();
        treeTwo = treeTwo.add(3, "3"); treeTwo = treeTwo.add(2, "2");
        assertEquals(2, treeTwo.size());

EmptyTree add method:

public NonEmptyTree<K, V> add(K key, V value) {  
    return new NonEmptyTree(key, value);
}

NonEmptyTree add method:

public NonEmptyTree<K, V> add(K key, V value) {
      if(this.key.compareTo(key) == 0) {
          this.value = value;
          return this;
      }
      else {
          if(key.compareTo(this.key) < 0) { 
              if(this.left.lookup(key) == null) {
                  this.left = new NonEmptyTree<K,V>(key, value);
                  return this;
              }
              else
                  return this.left.add(key, value);
          }
          else if(key.compareTo(this.key) > 0) { 
              if(this.right.lookup(key) == null) {
                  this.right = new NonEmptyTree<K,V>(key, value);
                  return this;
              }
              else
                  return this.right.add(key, value);
          }
      }
      return this;
  }

EmptyTree lookup:

public V lookup(K key) {
    return null;
  }

NonEmptyTree lookup:

public V lookup(K key) {
      if(key.compareTo(this.key) == 0)
          return this.value;
      else {
          if(key.compareTo(this.key) < 0)
              return this.left.lookup(key);
          if(key.compareTo(this.key) > 0) 
              return this.right.lookup(key);
      }

    return null;
  }