In Python: Define a function 'sprout_leaves' that, given a tree 't', and a list of values 'vals', returns a tree which is the same as 't', except that for every leaf that lives at the deepest level in the tree 't', it is given new children, one for each of the items in 'vals'. Do not add new children to non-leaf nodes or to tree nodes that are not at the deepest level. Below shows what doctest should be for reference.

def sprout_leaves(t, vals): """Sprout new leaves containing the data in vals at each of the deepest leaf in the original tree t and return the resulting tree. >>> t1 = tree(1, [tree(2), tree(3, tree(4))]) >>> print_tree(t1) 1 2 3 4 >>> new1 = sprout_leaves(t1, [5, 6]) >>> print_tree(new1) 1 2 3 4 5 6 >>> new2 = sprout_leaves(new1, [1, 2]) >>> print_tree(new2) 1 2 3 4 5 1 2 6 1 2