Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.63

Problem

Each of the following two procedures converts a binary tree to a list.

(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))

a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16 of the text?

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Solution, part A.

To answer this question, first consider the behavior of tree->list-1. It's a recursive definition. In the base case, when reaching the end of a branch of the tree, it returns the empty list. Otherwise, it recursively converts the left branch of the tree to a list and appends to it another list formed by consing the current element (e.g., (entry tree)) to the list generated by recursively converting the right branch of the tree. Because all elements to the left of the current element of a binary tree are smaller in magnitude than the current element, and all elements to the right of the current element are greater, this recursive plan will always build a list sorted from least to greatest element. tree->list-1 will produce the list (1 3 5 7 9 11) for all three trees in figure 2.16 of the text.

Now consider the behavior of tree->list-2. Like tree->list-1, it, too, is a recursive definition. In the base case it returns result-list; that is, the list that's been accumulated up to that point in the recursive computation. (The initial value of result-list is the empty list.) Otherwise, it recursively copies the right branch of the current element to a list; and then recusrively copies the left branch of the current element, using as the result-list the list created by consing the current element onto the front of the right branch list. Because it always conses the current element onto the front of the list created by copying the right branch (i.e., all values greater in magnitude than the current element), tree->list-2 will always to produce a list sorted from smallest to largest element. Therefore, the order in which elements occur in the final list is identical to the order produced by tree->list-1.

Solution, part B.

It's apparent from the behavior of both tree->list-1 and tree->list-2 that both procedures visit each element of the input tree exactly once, i.e., the number of visits grows as θ(n). Now we must determine how many operations are performed by each visit to determine the overall order of growth for the two procedures.

Let's consider tree->list-2 first. Other than recursive procedure calls, it only performs a cons at each step. As far as we know, cons has constant-factor growth (the reality is more complicated, but it depends on implementation details that we haven't covered at this point in the text yet), so the overall number of steps required by tree->list-2 grows as θ(n).

Analyzing tree->list-1 is more complicated, because it calls the append procedure. Each time tree->list-1 is invoked, it makes two recursive calls -- one for the left branch of the current element, and one for the right branch -- and also calls append and cons, once each. Because cons has constant-factor growth, we can ignore its effect on the overall order growth of tree->list-1. On the other hand, if you consult the definition of append in section 2.2.1, you'll see the order of growth of the append procedure is proportional to the length of its first list argument. In the definition of tree->list-1, the first argument to append is the list created by recursively converting the element's left branch from a tree to a list; therefore, the time it takes tree->list-1 to process each element of a binary tree is proportional to the number of sub-elements contained in its left branch.

In the worse case, if the tree is unbalanced such that each element in tree is greater than all of its sub-elements -- i.e., each node's right branch is empty, and all its sub-nodes are contained in the left branch -- then, when the top-level node in the tree is processed, first list argument to append contains n − 1 elements; the first list argument to append in the next node in the tree contains n − 2 elements, etc. So in this case, the number of operations performed for a left-unbalanced tree of this kind is (n − 1) + (n − 2) + (n − 3) + ... + 1. This sum is more compactly represented as $\sum_{k=1}^n (n-k) = 1/2 (n^2 - n)$. Therefore, for an unbalanced tree, tree->list-1 has θ(n2) growth.

However, the exercise asks us to find the order of growth in the number of steps required to convert a balanced tree, so this worst-case analysis does not apply. In a balanced binary tree, approximately only half of a node's sub-nodes are in the left branch, so append will only have to copy half of each node's sub-nodes. Since the number of copies performed is halved at each step, and there are n steps, the total number of steps performed by tree->list-1 on a balanced tree of size n grows as $\theta (n \cdot \log n)$.