Add Element to BST
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.
  #
  #=====================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def add( self, el ):
    n, p = self.root, None

    while n is not None and n.data != el:
      p = n
      if el < n.data:
        n = n.left
      else:
        n = n.right

    if n is None: # not duplicate
      if p is None:
        self.root = Node( el )
      elif el < p.data:
        p.left = Node( el )
      else:
        p.right = Node( el )

import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #===================================================================
  # 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.
  #===================================================================

  def testAdd( self ):
    bst = BST()
    el = [7, 9, 2, 4, 6, 7, 10, 1]
    self.assertEquals( True, bst.isEmpty() )
    self.assertEquals( 0, bst.size() )
    self.assertIsNone( bst.find( el[0] ) )

    for i in el:
      bst.add( i )

    self.assertEquals( False, bst.isEmpty() )
    self.assertEquals( len( el ) - 1, bst.size() ) # repeated 7
    self.assertIsNotNone( bst.find( el[3] ) )