"""
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 getChildren(t):
    result = []
    if t["left"] != None:
        leftT = t["left"]
        leftValue = leftT["contents"]
        result.append(leftValue)
    if t["right"] != None:
        rightT = t["right"]
        rightValue = rightT["contents"]
        result.append(rightValue)
    return result

t = { "contents" : 6,
      "left"  : { "contents" : 3,
                  "left"  : { "contents" : 8,
                              "left"  : None,
                              "right" : None },
                  "right" : { "contents" : 7,
                              "left"  : None,
                              "right" : None } },
      "right" : { "contents" : 2,
                  "left"  : None,
                  "right" : { "contents" : 9,
                              "left"  : None,
                              "right" : None } } }

print(getChildren(t))
print(getChildren(t["left"]))
print(getChildren(t["left"]["right"]))

###

def countNodes(t):
    if t["left"] == None and t["right"] == None:
        return 1
    else:
        count = 0
        if t["left"] != None:
            count += countNodes(t["left"])
        if t["right"] != None:
            count += countNodes(t["right"])
        return count + 1

print(countNodes(t))

###

def countNodes(t):
    if t == None:
        return 0
    else:
        count = 0
        count += countNodes(t["left"])
        count += countNodes(t["right"])
        return count + 1

print(countNodes(t))

###

def sumNodes(t):
    if t["left"] == None and t["right"] == None:
        return t["contents"]
    else:
        total = 0
        if t["left"] != None:
            total += sumNodes(t["left"])
        if t["right"] != None:
            total += sumNodes(t["right"])
        return total + t["contents"]

print(sumNodes(t))

###

def listValues(t):
    if t == None:
        return []
    else:
        result = []
        result = result + listValues(t["left"])
        result.append(t["contents"])
        result = result + listValues(t["right"])
        return result

print(listValues(t))

###

def getPastGen(t, n): # didn't get to this
    if n == 0:
        return [ t["contents"] ] # you're at the right generation
    else:
        result = []
        if t["left"] != None:
            result = result + getPastGen(t["left"], n-1) # go back one gen
        if t["right"] != None:
            result = result + getPastGen(t["right"], n-1)
        return result # don't include root - not a parent!

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

print(getPastGen(familyTree, 2))