Binary Search Tree in Java with Generics

This post is more about generics than the actual implementation of the binary search tree. I tried to implement some of the suggestions in the developerworks articles titled "Java theory and practice: Going wild with generics". The Binary Search Tree of this example uses the first two suggestions. The rest are equally helpful though.

1. A generic factory method that allows you to avoid redundantly specifying type parameters

   public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() 

   Can be used as shown below.

   BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();

2. By using bounded wildcards, we can now construct a tree with both the super and sub-class type objects.

   public class BinarySearchTree<T extends Comparable<? super T>> 

3. The get-put principle

   Use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you do both.

4. Wildcard capture: Use a generic method as a capture helper to workaround compiler's limitations dealing with wildcards. (refer to the article "Java theory and practice: Going wild with generics, Part 1")

Following is the complete source code

package trees;

import java.util.NoSuchElementException;

public class BinarySearchTree<T extends Comparable<? super T>> {

  private Entry<T> root;

  public BinarySearchTree() {
    root = null;
  }
  
  public static<T extends Comparable<? super T>> BinarySearchTree<T> createTestTree() {
    return new BinarySearchTree<T>();
  }

  public void insert(T value) {
    root = insert(value, root);
  }
  

  public void remove(T value) {
    root = remove(value, root);
  }

  public boolean contains(T value) {
    return valueOf(find(value, root)) != null;
  }

  private T valueOf(Entry<T> entry) {
    return entry == null ? null : entry.element;
  }

  private Entry<T> insert(T value, Entry<T> entry) {
    if (entry == null)
      entry = new Entry<T>(value);
    else if (value.compareTo(entry.element) < 0)
      entry.left = insert(value, entry.left);
    else if (value.compareTo(entry.element) > 0)
      entry.right = insert(value, entry.right);
    else
      throw new RuntimeException("Duplicate Entry : " + value.toString());
    return entry;
  }

  private Entry<T> remove(T value, Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException("Entry not found : " + value.toString());
    if (value.compareTo(entry.element) < 0)
      entry.left = remove(value, entry.left);
    else if (value.compareTo(entry.element) > 0)
      entry.right = remove(value, entry.right);
    else {
      // Entry found.
      if (entry.left != null && entry.right != null) {

        // Replace with in-order successor (the left-most child of the right subtree)
        entry.element = findMin(entry.right).element;
        entry.right = removeInorderSuccessor(entry.right);

        // Replace with in-order predecessor (the right-most child of the left subtree)
        // entry.element = findMax(entry.left).element;
        // entry.left = removeInorderPredecessor(entry.left);
      } else
        entry = (entry.left != null) ? entry.left : entry.right;
    }
    return entry;
  }

  private Entry<T> removeInorderSuccessor(Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException();
    else if (entry.left != null) {
      entry.left = removeInorderSuccessor(entry.left);
      return entry;
    } else
      return entry.right;
  }

  private Entry<T> removeInorderPredecessor(Entry<T> entry) {
    if (entry == null)
      throw new NoSuchElementException();
    else if (entry.right != null) {
      entry.right = removeInorderPredecessor(entry.right);
      return entry;
    } else
      return entry.left;
  }

  private Entry<T> findMin(Entry<T> entry) {
    if (entry != null)
      while (entry.left != null)
        entry = entry.left;

    return entry;
  }

  private Entry<T> findMax(Entry<T> entry) {
    if (entry != null)
      while (entry.right != null)
        entry = entry.right;

    return entry;
  }

  private Entry<T> find(T value, Entry<T> entry) {
    while (entry != null) {
      if (value.compareTo(entry.element) < 0)
        entry = entry.left;
      else if (value.compareTo(entry.element) > 0)
        entry = entry.right;
      else
        return entry;
    }

    return null;
  }

  private void printInOrder(Entry<T> entry) {
    if (entry != null) {
      printInOrder(entry.left);
      System.out.println(entry.element);
      printInOrder(entry.right);
    }
  }

  public void printInOrder() {
    printInOrder(root);
  }

  private static class Entry<T extends Comparable<? super T>> {
    T element;
    Entry<T> left;
    Entry<T> right;

    Entry(T theElement) {
      element = theElement;
      left = right = null;
    }
  }

  private static class Test implements Comparable<Test> {
    private String value;

    public Test(String value) {
      this.value = value;
    }

    public String toString() {
      return value;
    }

    @Override
    public int compareTo(Test o) {
      return this.value.compareTo(o.toString());
    }
  }

  private static class Test1 extends Test {
    public Test1(String value) {
      super(value);
    }
  }

  public static void main(String[] args) {
    BinarySearchTree<Test> tree = BinarySearchTree.createTestTree();
    int size = 20;

    for (int i = 0; i <= size; i++) {
      tree.insert(new Test1(String.valueOf(i)));
    }

    tree.insert(new Test1("100"));
    tree.remove(new Test1("10"));
    tree.remove(new Test1(String.valueOf(15)));
    tree.remove(new Test1(String.valueOf(20)));
    tree.printInOrder();
    System.out.println("Contains (10) : " + tree.contains(new Test1("10")));
    System.out.println("Contains (11) : " + tree.contains(new Test1(String.valueOf(11))));
  }

}

References

• Java theory and practice: Going wild with generics, Part 1
  
• Java theory and practice: Going wild with generics, Part 2
• Java theory and practice: Generics gotchas