Problem 3.5: Decorate Christmas Tree (100 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 every branches are the same and all its branches are balanced. For example, the left tree is balanced but the right one is not.

2_3_5

Isla wants to buy more gifts and hang them on the tree to balance it. Help her implement balance_tree, which takes in a tree 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 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 ***"