Height of BST
by Isai Damier, Android Engineer @ Google

  #=====================================================================
  # Author: Isai Damier
  # Title: Height
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Description: Calculate the height of the given tree. This
  #    method returns the size of the longest path from the self.root
  #    to a leaf.
  #
  # Alternate Algorithm: If built-in function is acceptable,
  #    then the recursive portion of the algorithm may be as
  #    below:
  #     def height(self, n):
  #      if n is None:
  #        return 0
  #      return 1 + max(height(n.left), height(n.right))
  #
  #=====================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def height( self ):
    return self._height( self.root )

  def _height( self, n ):
    if n is None:
      return 0
    l = self._height( n.left )
    r = self._height( n.right )
    return 1 + ( l if l > r else r ) # highest subtree plus self

import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #===================================================================
  # Test of height method, of class BST.
  #===================================================================
  def testHeight( self ):
    bst = BST()

    treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
                      175, 225, 275, 325, 375, 35, 212, 312, 400]
    self.assertEquals( 0, bst.height() )
    # set expectation
    expected = 5 # draw the tree on paper

    # load data into tree
    for i in treeTape:
      bst.add( i )

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size

    # test height
    self.assertEquals( expected, bst.height() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size