Study Guide: Mutable Trees

Instructions

This is a study guide with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.

Assignments

Important: For solutions to these assignments once they have been released, see the main website

• Hw 5
• Lab 8

Handouts

• Discussion 7

Lectures

• Representation

Readings

• Section 2.9

Guides

Mutable Trees

Trees are a hierarchical data structure. Previously in this class, we represented tree-like structures using functional abstraction with the tree constructor and label and branches selectors. If we wanted to 'change' the values in the tree abstraction, we would need to create an entirely new tree with the desired values.

But classes allow us to modify the values in a tree in-place using mutation, without needing to create new objects. We can reassign to t.label or t.branches, things that we couldn't do previously with the tree functional abstraction.

>>> t = Tree(1)
>>> t.label
1
>>> t.label = 2
>>> t.label
2

The best way to model trees is by drawing tree diagrams like we saw in lecture. Each node in a tree is represented with a circle and contains its label value and a list of branches.

All of our previous knowledge of trees still applies. The tree problems that we usually try to solve still involve tree traversal where we visit each node in the tree and perform some computations as we visit. For example, we can define a function square_tree which takes in a mutable Tree and squares each value in the tree.

def square_tree(t):
    t.label = t.label ** 2
    for b in t.branches:
        square_tree(b)

But tree mutation problems can come in many different shapes and forms and require us to pay special attention to fundamentals like domain and range.

For example, here are two ways of defining a function, prune_2, which removes the last two branches of each node in the tree. The general strategy is to replace each node's branches with a new list of branches containing only the desired branches. One way to do this would be to call prune_2 on each branch we'd like to keep.

def prune_2(t):
    t.branches = [prune_2(b) for b in t.branches[:2]]
    return t

Notice that we had to return the input tree, t. Why is this necessary?

Another way would be to first prune the branches, and then loop over the remaining branches. This has the advantage that it makes it clear to the person using this program that a new tree is not created.

def prune_2(t):
    t.branches = t.branches[:2]
    for b in t.branches:
        prune_2(b)

Practice Problems

Easy

Q1: Same Shape

Write a function same_shape that returns True if two Trees have the same shape. Two trees have the same shape if and only if they have the exact same structure of branches and nodes. Each branch and node in one Tree should correspond to a branch or node in the other Tree.

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape if they have the exact same structure of branches and nodes.
    Each branch and node in t1 should correspond to a branch or node
    in t2.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = Tree(4, [Tree(3, [Tree(2, [Tree(1)])])])
    >>> same_shape(t, s)
    False
    """
    "*** YOUR CODE HERE ***"
    return len(t1.branches) == len(t2.branches) and \
		all([same_shape(b1, b2) for b1, b2 in zip(t1.branches, t2.branches)])

Toggle Solution