class SumTree:
    def __init__(self):
        self.root = None

class Node:
    def __init__(self):
        self.key = 0
        self.left = None
        self.right = None

def makeNode(key):
    n = Node()
    n.key = key
    return n

def build_sum_tree(array):
    return build_sum_tree2(array, 0, len(array))

def build_sum_tree2(array, startpos, length):
    tree.root = array[startpos]
    if length < 1:
        return None
    if length == 1:
        makeNode(array[startpos])
        return tree
    halflen = length/2
    l = build_sum_tree2(array, startpos, halflen)
    r = build_sum_tree2(array, startpos+halflen, length-halflen)
    tree. = makeNode(l.key + r.key)
    n.left = l
    n.right = r
    return tree

def is_sum_tree(tree):
    if tree.root == None:
        return True
    if is_sum_tree2(tree.root) == False:
        return False
    elif is_sum_tree2(tree.root) == None:
        return True

def is_sum_tree2(node):
    if node.left is not None and node.right is not None:
        if node.key != node.left.key + node.right.key:
            return False
        is_sum_tree2(node.right)
        is_sum_tree2(node.left)
    elif node.left is None and node.right is not None:
        return False
    elif node.left is not None and node.right is None:
        return False
    else:
        pass