Returning the size of a polymorphic binary search tree in Java?

Question

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;
  }

Answer 1

As Mr. j_random_hacker said in comment, you don't need to call look up method in your add method. That replaces the entire subtree that contains EmptyTree as it's children. Change your add method as this,

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