Discussion 13 Guide

Discussion 13 Guide

3.2: Question 2

4: Question 2

Section 3.2 Question 2

Write a program flatten that given a Tree t, will return a linked list of the elements of t, ordered by level. Entries on the same level should be ordered from left to right. For example, the following tree will return the linked list <1 2 3 4 5 6 7>.

This problem actually touches on a concept that is not covered in this course called breadth first search. Take 61B for more info!

We can approach this problem in two ways, using just a list, or traversing the tree twice:

1. To give each node a "level"
2. To put together our linked list, based on the levels we assigned each
   node.

Intuitive Approach

Let’s first try the intuitive approach, which is to traverse t twice. On the first traversal, I will have to keep track of the level of every node. Let’s do this with a dictionary that keeps a list of each node at a level (which will be the key).

levels = {}
define traverser(t, level)
    if level not in levels:
        levels[level] = []
    levels[level].append(t)
    [traverser(c, level + 1) for c in t.children]

Now that we have all of our levels (and conveniently, the nodes on the same level will be ordered from left to right because we traverse our children from left to right), we just have to stick it into a Linked List. This part is a little messy.

list_of_nodes = []
for l in range(len(levels)): # dictionaries are unordered!
    for n in levels[l]:
        list_of_nodes.append(n.entry)

def converter(lst):
    if not lst:
        return Link.empty
    return Link(lst[0], converter(lst[1:]))

converter(list_of_nodes)

Putting it together:

define flatten(t):
    levels = {}
    define traverser(t, level)
        if level not in levels:
            levels[level] = []
        levels[level].append(t)
        [traverser(c, level + 1) for c in t.children]
    traverser(t, 0)
    list_of_nodes = []
    for l in range(len(levels)): # dictionaries are unordered!
        for n in levels[l]:
            list_of_nodes.append(n.entry)

    def converter(lst):
        if not lst:
            return Link.empty
        return Link(lst[0], converter(lst[1:]))

    converter(list_of_nodes)

Approach with List (Queue)

Now let’s go over a way to solve this problem with only a list. The key understanding is that when we traverse a tree, it’s possible to make a list of the nodes in the order that we want.

For example, when we start at the root node, we can form a list of nodes (children) that we will want to collect entries from. At the root node 1, we can form a list, or a queue, of nodes to traverse next - the nodes 2, 3, and 4. If this list can be mutated by each function call, we can use this list to figure out which node to look at next.

In the simplest case, our list, after traversing the root node’s children would be [2, 3, 4] (we will traverse the node 2 next). After we traverse the node 2, we would just tack on what we have to explore (2’s children) to the end of our list. So our list of nodes we still need to explore would look like this:

[3, 4, 5, 6] # we explored node 2 already

Now that we have the order of exploration down, we can just return the Linked List of the current entry, and a recursive call to our helper function. Putting that together:

define flatten(t):
    def flatten_helper(queue):
        if not queue: # queue is empty, we're done exploring
            return Link.empty
        curr = queue.pop(0) # removes the first element of the queue
        for c in curr.children:
            queue.append(c) # we add future nodes to explore to the end
        return Link(curr.entry, flatten_helper(queue))
    return flatten_helper([t]) # start it off with the root node

Section 4 Question 2

Define deep-apply, which takes a nested list and applies a given procedure to every element. deep-apply should return a nested list with the same structure as the input list, but with each element replaced by the result of applying the given procedure to that element. Use the built-in list? procedure to detect whether a value is a list. The procedure map has been defined for you.

(define (map fn lst)
    (if (null? lst)
        nil
        (cons (fn (car lst)) (map fn (cdr lst)))))

This problem is kind of similar to replace_all_deep (Section 1 Q#2). However, with the provided map function, we eliminate having to process element by element.

Let’s look at the case where the list is not deep:

(define (deep-apply fn lst)
    (map fn lst))

If we map deep-apply over every element, we don’t need to worry about checking if (car nested-list) is a list, because map is calling deep-apply on each element individually. Thus, we only need to check if nested-list is a list. If it is, we need to map deep-apply over it. If it’s not, we are returning (fn nested-list). This might be a little more intuitive if you replace the argument name nested-list with elem.

We get:

(define (deep-apply fn nested-list)
    (if (list? nested-list)
        (map (lambda (x) (deep-apply fn x)) nested-list)
        (fn nested-list)))