Add Trees(A CS61A Lab Problem)

Lei Yan

2019/03/20

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:

  1. If both t1 and t2 are leaves.
  2. If one of the two trees is leaf but not the another.
  3. Both trees are not leaves, but have the same number of branches.
  4. 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)])