Add
by Isai Damier, Android Engineer @ Google

/*****************************************************************
 * Author: Isai Damier
 * Title: Add
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Add an element to a Binary Search Tree.
 *
 * Time Complexity of Solution:
 *   Best = const; Average = O(log(n)); Worst = O(n).
 *
 * Description:
 *   This function does not admit duplicate data into the BST.
 *
 ****************************************************************/ 
 public void add(int el, Node root) {
  Node n = root, p = null;

  while (null != n && n.data != el) {
    p = n;
    if (el < n.data) {
      n = n.left;
    } else {
      n = n.right;
    }
  }

  if (null == n) {// not duplicate
    if (null == p) {
      root = new Node(el);
    } else if (el < p.data) {
      p.left = new Node(el);
    } else {
      p.right = new Node(el);
    }
  }
}

import org.junit.Test;
import static org.junit.Assert.*;
public class BSTTest {

  /***********************************************************************
   * There is really no direct way to test the add method of a BST except
   * through testing some other methods of the BST: such as isEmpty, size,
   * find, delete, etc. Basically, after adding an element, it can be
   * checked whether that element is present on the tree.
   **********************************************************************/
  @Test
  public void testAdd() {
    System.out.println(""add"");
    int el = 7;
    BST bst = new BST();
    assertEquals(true, bst.isEmpty());
    assertEquals(0, bst.size());
    assertNull(bst.find(el));

    bst.add(el);

    assertEquals(false, bst.isEmpty());
    assertEquals(1, bst.size());
    assertNotNull(bst.find(el));
  }
}