def getChildren(t):
    result = []
    leftT = t["left"]
    if leftT != None:
        result.append(leftT["contents"])
    rightT = t["right"]
    if rightT != None:
        result.append(rightT["contents"])
    return result


# Counting nodes using a base case of a leaf
def countNodes(t):
    if t["left"] == None and t["right"] == None:
        return 1
    else: #recursive case
        total = 1
        if t["left"] != None:
            total += countNodes(t["left"])
        if t["right"] != None:
            total += countNodes(t["right"])
        return total

# Counting nodes using a base case of an empty tree
def countNodesOther(t):
    if t == None:
        return 0
    else:
        count = 0
        count += countNodesOther(t["left"])
        count += countNodesOther(t["right"])
        return count + 1

def listValues(t):
    if t["left"] == None and t["right"] == None :
        return [t["contents"]]
    else:
        result = []
        if t["left"] != None:
            result = result + listValues(t["left"])
            
        # Note that putting this line here means the items are in left-to-right order!
        result.append(t["contents"])
        
        if t["right"] != None:
            result = result + listValues(t["right"])
        return result


# See slide 13 in lecture 7-2 for a visual representation of this tree
# Try drawing it yourself first! It's good practice :)
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("Children of root:", getChildren(t))
print("Children of node 3:", getChildren(t["left"]))
print("Children of node 2:", getChildren(t["right"]))

print("Count of nodes:", countNodes(t))
print("Count of nodes using different base case:", countNodesOther(t))

print("List of all nodes from left to right:", listValues(t))