Size
by Isai Damier, Android Engineer @ Google

/****************************************************************
 * Author: Isai Damier
 * Title: Size
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Indicate the number of nodes in this BST.
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 *
 * Technical Details: This function is certainly among the most
 *    doltish methods for tracking the size of a BST: it traverses
 *    the tree each time size is needed. In creating a BST, it is
 *    more sensible to create a size field and track the tree by
 *    incrementing size inside the add function and decrementing
 *    it inside the delete and clear functions. All the same,
 *    writing this function makes for good exercise.
 *
 ****************************************************************/ 
 public int size() {
  Node n = root;
  int size = 0;
  Stack<Node> stack = new Stack<Node>();
  while (!stack.isEmpty() || null != n) {
    if (null != n) {
      stack.push(n);
      n = n.left;
    } else {
      size++;
      n = stack.pop();
      n = n.right;
    }
  }
  return size;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/**
   * Test of size method, of class BST.
   */
  @Test
  public void testSize() {
    System.out.println(""size"");
    BST bst = new BST();
    assertEquals(0, bst.size());
    int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());
  }
}