## **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 `cons`ing 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 `cons`ing the current element onto the front of the right branch list. Because it always `cons`es 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 . Therefore, for an *unbalanced* tree, `tree->list-1`

has θ(*n*^{2}) 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 .