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):
    if length < 1:
        return None
    if length == 1:
        return makeNode(array[startpos])
    halflen = length/2
    l = build_sum_tree2(array, startpos, halflen)
    r = build_sum_tree2(array, startpos+halflen, length-halflen)
    n = makeNode(l.key + r.key)
    n.left = l
    n.right = r
    return n

def is_sum_tree(tree):
    if tree == None:
        return True
    if tree.left is None or tree.right is None:
        pass
    else:
        if tree.key != tree.left.key + tree.right.key:
            return False
        else:
            is_sum_tree(tree.right)
            is_sum_tree(tree.left)
    return True