Problem 5: Decorate Christmas Tree (0 pts)

Christmas is coming soon. Isla bought a Christmas tree for Tsukasa. A Christmas tree is a Tree instance. There are some gifts on every nodes of the tree, and the label of each node is the number of gifts on it. Every gifts have the same weight.

We say a tree is balanced if it is a leaf or the total weight of its every branches are the same and all its branches are balanced. For example, the left tree is balanced but the right one is not.

3_2

Isla wants to buy more gifts and hang them on the tree to balance it. Please help her implement balance_tree, which takes in a tree t and hangs gifts as few as possible on it to balance it.

Note: For trees which have more than one ways to balance with the same minimum number of gifts, you can choose any one of them as result and it won't influence your score.

def balance_tree(t):
    """Balance a tree.

    >>> t1 = Tree(1, [Tree(2, [Tree(2), Tree(3), Tree(3)]), Tree(2, [Tree(4), Tree(4)])])
    >>> balance_tree(t1)
    >>> t1
    Tree(1, [Tree(2, [Tree(3), Tree(3), Tree(3)]), Tree(3, [Tree(4), Tree(4)])])
    """
    "*** YOUR CODE HERE ***"