"""
Learning Goals:
 - Identify core parts of trees, including nodes, children, the root, and leaves
 - Use binary trees implemented with dictionaries when reading and writing code
"""

def sumTree(t):
    if t["left"] == None and t["right"] == None:
        return t["value"]
    else:
        result = t["value"]
        if t["left"] != None:
            result = result + sumTree(t["left"])
        if t["right"] != None:
            result = result + sumTree(t["right"])
        return result

def sumTree(t):
    result = t["value"]
    if t["left"] != None:
        result = result + sumTree(t["left"])
    if t["right"] != None:
        result = result + sumTree(t["right"])
    return result

def sumTree(t):
    if t == None:
        return 0
    else:
        leftResult = sumTree(t["left"])
        rightResult = sumTree(t["right"])
        return t["value"] + leftResult + rightResult

####

def listNodes(t):
    if t["left"] == None and t["right"] == None:
        return [ t["value"] ]
    else:
        result = [ ]
        if t["left"] != None:
            result = result + listNodes(t["left"])
        result = result + [ t["value"] ]
        if t["right"] != None:
            result = result + listNodes(t["right"])
        return result

####

example = {
    "value" : 6,
    "left"  : { "value" : 3,
                "left"  : { "value" : 8,
                            "left"  : None,
                            "right" : None },
                "right" : { "value" : 7,
                            "left"  : None,
                            "right" : None } },
    "right" : { "value" : 2,
                "left"  : None,
                "right" : { "value" : 9,
                            "left"  : None,
                            "right" : None } } }

print(sumTree(example))
print(listNodes(example))

####

def getPastGen(t, n):
    if n == 0:
        return [ t["value"] ]
    else:
        gen = [ ]
        if t["left"] != None:
            gen += getPastGen(t["left"], n-1)
        if t["right"] != None:
            gen += getPastGen(t["right"], n-1)
        return gen

familyTree = {
    "value" : "Arya",
    "left"  : { "value" : "Ned",
                "left"  : { "value" : "Rickard",
                            "left"  : None, "right" : None },
                "right" : { "value" : "Lyarra",
                            "left"  : None, "right" : None } },
    "right" : { "value" : "Catelyn",
                "left"  : { "value" : "Hoster",
                            "left"  : None, "right" : None },
                "right" : { "value" : "Minisa",
                            "left"  : None, "right" : None } } }

print(getPastGen(familyTree, 2))