#################################################
# hw10.py
#
# Note: to receive any credit on this hw, you must not use
# 'for' or 'while' loops anywhere!  Just use recursion here!
#
#################################################

def preOrderString(tree, position, s):
    return ''

def countNodes(tree, position):
    return 0

def inBST(tree, position, target):
    return False

######################################################################
# bonus/optional: you can ignore the functions below here
######################################################################

def countLeaves(tree, position):
    return 0

######################################################################
# ignore_rest: The autograder will ignore all code below here
######################################################################

#################################################
# Test Functions
#################################################

def testPreOrderString():
    print('Testing preOrderString()...', end='')
    assert(preOrderString([ ], 1, '') == '')
    assert(preOrderString([None,'B','A','M',None,None], 1, '') == 'BAM')
    assert(preOrderString([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1, '') == 'MADSRZ')
    print('Passed')

def testCountNodes():
    print('Testing countNodes()...', end='')
    assert(countNodes([], 1) == 0)
    assert(countNodes([None,'M',None,None], 1) == 1)
    assert(countNodes([None,'B','A','M',None,None], 1) == 3)
    assert(countNodes([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1) == 6)
    print('Passed!')

def testInBST():
    print('Testing inBST()...', end='')
    assert(inBST([], 1, 'Z') == False)
    assert(inBST([None,'M',None,None], 1, 'M') == True)
    assert(inBST([None,'M',None,None], 1, 'Z') == False)
    for ch in 'ADMRSZ':
        assert(inBST([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1, ch) == True)
    assert(inBST([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1, 'Y') == False)
    assert(inBST([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1, 'B') == False)
    print('Passed')

def bonusTestCountLeaves():
    print('Testing bonus: countLeaves()...', end='')
    assert(countLeaves([], 1) == 0)
    assert(countLeaves([None,'M',None,None], 1) == 1)
    assert(countLeaves([None,'B','A','M',None,None], 1) == 2)
    assert(countLeaves([None,'M','A','S',None,'D','R','Z',None,None,None,None,None,None,None,None,None,None], 1) == 3)
    print('Passed')

#################################################
# testAll and main
#################################################

def testAll():
    testPreOrderString()
    testCountNodes()
    testInBST()
    #bonusTestCountLeaves()

if __name__ == '__main__':
    testAll()