# Sum Single Children of BSTby 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
```