class TreeNode :
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def construct_tree(txt_file_path):
    node_arr = []
    parent_arr = []

    root = None
    f = open(txt_file_path, "r")
    for idx, line in enumerate(f):
        if idx == 0:
            root = TreeNode(int(line[0]))
            parent_arr.append(root)
        else:
            arr = line.split()
            for elt in arr:
                node_arr.append(TreeNode(int(elt)))
            for i, parent_elt in enumerate(parent_arr):
                parent_elt.left = node_arr[i]
                parent_elt.right = node_arr[i + 1]

            parent_arr = node_arr
            node_arr = []
    return root


def getRootToLeafSum(root):
    # base case: tree is empty
    if root is None:
        return 0

    # calculate the maximum node-to-leaf sum for the left child
    left = getRootToLeafSum(root.left)

    # calculate the maximum node-to-leaf sum for the right child
    right = getRootToLeafSum(root.right)

    # consider the maximum sum child
    return (left if left > right else right) + root.data


if __name__ == "__main__":
    root = construct_tree("input1.txt")
    sum = getRootToLeafSum(root)
    print(sum)