Sum Single Children of BST
by Isai Damier, Android Engineer @ Google

  #=====================================================================
  # Author: Isai Damier
  # Title: Sum Single Children of BST
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Description: Not every node in a BST has two children. A node
  #    may have no children at all (e.g. a leaf) or a node may
  #    have a single child. This function aggregates the values
  #    of all nodes that are single children. If the tree is None,
  #    the function returns -1.
  #
  # Technical Details: In this implementation, the self.root of the
  #     tree is counted as a single child.
  #
  #=====================================================================
 
 
import Queue
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def sumSingleChildren( self ) :
    if self.root is None:
      return -1

    queue = Queue.Queue()
    queue.put( self.root )
    n = None
    tally = self.root.data # the self.root is a single child
    while not queue.empty():
      n = queue.get() # dequeue
      if n.left is not None and n.right is not None: # nothing to add
        queue.put( n.left )
        queue.put( n.right )
      elif n.left is not None:
        tally += n.left.data
        queue.put( n.left )
      elif n.right is not None:
        tally += n.right.data
        queue.put( n.right )

    return tally

import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #=======================================================================
  # Test of sumSingleChildren method, of class BST.
  #=======================================================================
  def testSumSingleChildren( 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( -1, bst.sumSingleChildren() )
    # set expectation
    expected = 200 + 35 + 212 + 312 + 400 # 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 sumSingleChildren
    self.assertEquals( expected, bst.sumSingleChildren() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size