binary search tree in java

BinarySearchTree.java

import java.util.Iterator;
import java.util.LinkedList;

public class BinarySearchTree<T extends Comparable<T>> implements Iterable<T> {

  // tree node
  class Node {
    T value;
    Node leftChild;
    Node rightChild;

    // assumption: left < value < right

    Node(T value) {
      this.value = value;
    }
  }

  // position of child, for remove
  enum ChildPostion {
    ROOT, // current node is root
    LEFT, // current node is left child of parent node
    RIGHT; // current node is right child of parent node
  }

  private Node root;

  /**
   * Test if element in tree.
   * 
   * @param x element
   * @return true if contains, otherwise false
   */
  public boolean contains(T x) {
    return contains(x, root);
  }

  private boolean contains(T x, Node node) {
    if (node == null) return false;
    int relation = x.compareTo(node.value);
    if (relation == 0 /* equal */) return true;
    if (relation < 0 /* less than */) return contains(x, node.leftChild);
    return contains(x, node.rightChild);
  }

  /**
   * Insert multiple elements.
   * 
   * @param xs elements
   */
  public void insert(T... xs) {
    for (T x : xs) {
      insert(x);
    }
  }

  /**
   * Insert element into tree.
   * 
   * @param x element to insert
   */
  public void insert(T x) {
    if (root == null)
      root = new Node(x);
    else
      insert(x, root);
  }

  private void insert(T x, Node node) {
    int relation = x.compareTo(node.value);
    if (relation == 0 /* equal */)
      throw new IllegalArgumentException("duplicated element [" + x + "]");
    if (relation < 0 /* less than */) {
      if (node.leftChild == null) {
        node.leftChild = new Node(x);
      } else {
        insert(x, node.leftChild);
      }
    } else {
      // greater than
      if (node.rightChild == null) {
        node.rightChild = new Node(x);
      } else {
        insert(x, node.rightChild);
      }
    }
  }

  /**
   * Insert element into tree.
   * 
   * @param x element to insert
   */
  public void insert2(T x) {
    root = insert2(x, root);
  }

  private Node insert2(T x, Node node) {
    if (node == null) return new Node(x);
    int relation = x.compareTo(node.value);
    if (relation == 0 /* equal */)
      throw new IllegalArgumentException("duplicated element [" + x + "]");
    if (relation < 0 /* less than */) {
      node.leftChild = insert2(x, node.leftChild);
    } else {
      // greater than
      node.rightChild = insert2(x, node.rightChild);
    }
    // no node created, just return node itself
    return node;
  }

  /**
   * Remove element.
   * 
   * @param x element to remove
   */
  public void remove(T x) {
    if (root == null) throw new IllegalStateException("empty tree");
    remove(x, root, null, ChildPostion.ROOT);
  }

  private void remove(T x, Node node, Node parent, ChildPostion position) {
    if (node == null) return; // no such element, do nothing
    int relation = x.compareTo(node.value);
    if (relation < 0 /* less than */) {
      remove(x, node.leftChild, node, ChildPostion.LEFT);
    } else if (relation > 0 /* greater than */) {
      remove(x, node.rightChild, node, ChildPostion.RIGHT);
    } else {
      // current one is the node contains the element to be removed
      remove(node, parent, position);
    }
  }

  private void remove(Node node, Node parent, ChildPostion position) {
    if (node.leftChild == null) {
      if (node.rightChild == null) {
        // case 1: no child, just remove node itself
        connectNode(parent, position, null);
      } else {
        // case 2: only right child presents
        // connect parent to right child
        connectNode(parent, position, node.rightChild);
      }
    } else {
      // left child presents
      if (node.rightChild == null) {
        // case 2: only left child presents
        // connect parent to left child
        connectNode(parent, position, node.leftChild);
      } else {
        // case 3: left and right child both present
        // find in-order successor
        // node contains minimum value in right child tree
        Node min = node.rightChild;
        Node minParent = node;
        while (min.leftChild != null) {
          minParent = min;
          min = min.leftChild;
        }
        // replace value
        node.value = min.value;
        // remove in-order successor
        ChildPostion minPosition =
            minParent == node ? ChildPostion.RIGHT : ChildPostion.LEFT;
        remove(min, minParent, minPosition);
      }
    }
  }

  private void connectNode(Node parent, ChildPostion position, Node newChild) {
    switch (position) {
      case ROOT:
        root = newChild;
        break;
      case LEFT:
        parent.leftChild = newChild;
        break;
      case RIGHT:
        parent.rightChild = newChild;
        break;
      default:
        throw new IllegalArgumentException("unexpected child position ["
            + position + "]");
    }
  }

  public Iterator<T> iterator() {
    return inorderIterator();
  }

  // in-order iterator
  class InOrderIterator implements Iterator<T> {

    class NodeWithStatus {

      Node node;
      boolean expanded;

      NodeWithStatus(Node node, boolean expanded) {
        this.node = node;
        this.expanded = expanded;
      }

      T getValue() {
        return node.value;
      }

      boolean isEmpty() {
        return node == null;
      }

    }

    private LinkedList<NodeWithStatus> stack;

    public InOrderIterator(Node node) {
      stack = new LinkedList<NodeWithStatus>();
      pushItem(unexpandedNode(root));
    }

    private void pushItem(NodeWithStatus item) {
      if (!item.isEmpty()) {
        stack.push(item);
      }
    }

    private NodeWithStatus unexpandedNode(Node node) {
      return new NodeWithStatus(node, false);
    }

    private NodeWithStatus expandedNode(Node node) {
      return new NodeWithStatus(node, true);
    }


    public boolean hasNext() {
      return !stack.isEmpty();
    }

    public T next() {
      if (!hasNext()) throw new IllegalStateException("no next element");
      NodeWithStatus item;
      while (!(item = stack.pop()).expanded) {
        Node node = item.node;
        pushItem(unexpandedNode(node.rightChild));
        pushItem(expandedNode(node));
        pushItem(unexpandedNode(node.leftChild));
      }
      return item.getValue();
    }

    public void remove() {
      throw new UnsupportedOperationException("unsupported operation");
    }

  }

  public Iterator<T> inorderIterator() {
    return new InOrderIterator(root);
  }
}