t1 = { "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 } } }

t2 = { "contents" : 2,
      "left"  : None,
      "right" : { "contents" : 9,
                  "left"  : None,
                  "right" : None } }

###

def getChildren(t):
    childValues = []
    if t["left"] != None:
        tLeft = t["left"]
        childValues.append(tLeft["contents"])
    if t["right"] != None:
        tRight = t["right"]
        childValues.append(tRight["contents"])
    return childValues

#print(getChildren(t1))
#print(getChildren(t2))

###

def countValues(t):
    if t["left"] == None and t["right"] == None:
        print(1)
        return 1
    else:
        result = 0
        if t["left"] != None:
            print("Go left")
            result = result + countValues(t["left"])
        if t["right"] != None:
            print("Go right")
            result = result + countValues(t["right"])
        print(result + 1)
        return result + 1

#print(countValues(t1))

def countValues2(t):
    if t == None:
        print(0)
        return 0
    else:
        result = 0
        print("Go left")
        result = result + countValues2(t["left"])
        print("Go right")
        result = result + countValues2(t["right"])
        print(result + 1)
        return result + 1

#print(countValues2(t1))

###

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

###

"""You do: write the function listValues(t), which takes a tree and returns a
list of all the values in the tree. The values can be in any order, but try to
put them in left-to-right order if possible."""

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

print(listValues(t1))