### If you want to learn this course, please click here.

### This problem is lab05 Q9 of the above course.

Here is the problem description:

Define the function

`add_trees`

, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

First, here is my solution:

```
def add_trees(t1, t2):
#if is_leaf(t1) and is_leaf(t2):
#return tree(label(t1) + label(t2))
#elif is_leaf(t1) and not is_leaf(t2):
#return tree(label(t1) + label(t2), branches(t2))
#elif is_leaf(t2) and not is_leaf(t1):
#return tree(t2, t1)
len_1, len_2 = len(branches(t1)), len(branches(t2))
if len_1 == len_2:
return tree(label(t1) + label(t2), [add_trees(b1, b2) for b1, b2 in zip(branches(t1), branches(t2))])
elif len_1 < len_2:
branches_t1 = branches(t1) + [tree(0) for _ in range(len_2 - len_1)]
new_t1 = tree(label(t1), branches_t1)
return add_trees(new_t1, t2)
else:
return add_trees(t2, t1)
```

For clarity, I delted the doctest.

What you see is the second version of my solution. The first version has three more `if/else`

as you can see in the comments. Let’s analyse this piece of code!

Please consider these four situations:

- If both t1 and t2 are leaves.
- If one of the two trees is leaf but not the another.
- Both trees are not leaves, but have the
**same**number of branches. - Both trees are not leaves, but have
**different**numbers of branches.

Both situation 1 and 2 can be easily solved, see the comments of my code.

Situation 3 is actually not hard too, because you have the **same** number of branches, so `zip(branches(t1), branches(t2))`

works well. And hence you can add the roots of two trees and invoke recursive call on each pair of branches of the two trees.

#### The real challenge is situation 4

At first, I don’t know how to tackle this problem, so I went to lunch. I have been thinking about this problem on my way to the cafeteria. When I came back, a flash of inspiration provided the major breakthrough: **If the numbers of branches are different, I can just add number 0 to that smaller tree to make these two trees have the same number of branches!**

OK, problem solved! But wait, situation 1(2) seems to be a special case of situation 3(4)! So, after I deleted the code of situation 1 and 2, I got the present version.

Code below is a definition of tree ADT.

```
def tree(label, branches=[]):
"""Construct a tree with the given label value and a list of branches."""
for branch in branches:
assert is_tree(branch), 'branches must be trees'
return [label] + list(branches)
def label(tree):
"""Return the label value of a tree."""
return tree[0]
def branches(tree):
"""Return the list of branches of the given tree."""
return tree[1:]
def is_tree(tree):
"""Returns True if the given tree is a tree, and False otherwise."""
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
"""Returns True if the given tree's list of branches is empty, and False
otherwise.
"""
return not branches(tree)
def print_tree(t, indent=0):
"""Print a representation of this tree in which each node is
indented by two spaces times its depth from the root.
>>> print_tree(tree(1))
1
>>> print_tree(tree(1, [tree(2)]))
1
2
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
"""
print(' ' * indent + str(label(t)))
for b in branches(t):
print_tree(b, indent + 1)
def copy_tree(t):
"""Returns a copy of t. Only for testing purposes.
>>> t = tree(5)
>>> copy = copy_tree(t)
>>> t = tree(6)
>>> print_tree(copy)
5
"""
return tree(label(t), [copy_tree(b) for b in branches(t)])
```