## **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.64

## Problem

The following procedure `list->tree` converts an ordered list to a balanced binary tree.
The helper procedure `partial-tree` takes as arguments an integer *n* and list of at least *n* elements and
constructs a balanced tree containing the first *n* elements of the list. The result returned by `partial-tree` is a pair (formed with `cons`) whose `car` is the constructed tree and whose `cdr` is the list of elements not included in the tree.

(define (list->tree elements) (car (partial-tree elements (length elements)))) (define (partial-tree elts n) (if (= n 0) (cons '() elts) (let ((left-size (quotient (- n 1) 2))) (let ((left-result (partial-tree elts left-size))) (let ((left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1)))) (let ((this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size))) (let ((right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts))))))))

a. Write a short paragraph explaining as clearly as you can how `partial-tree` works. Draw the tree
produced by `list->tree` for the list `(1 3 5 7 9 11)`.

b. What is the order of growth in the number of steps required by `list->tree` to convert a list of *n*
elements?

## Solution, part A.

`partial-tree` divides its input list into 3 parts: a new list containing the first (*n* − 1) / 2 elements in the list, the middle element of the list, and another list containing the remaining elements. The two new lists are created recursively by applying `partial-tree` to each half of the input list. (The middle element is simply the `car` of the list of elements remaining after creating the first new list.) If the list is empty, `partial-tree` returns an empty list, which corresponds to the end of a branch. Because the input list is ordered, all of the elements in the first new list are smaller in magnitude than the middle element, and all of the elements in the second new list are greater than the middle element. It then creates a balanced tree rooted at the middle element whose left branch is the first new list and whose right branch is the second new list. Because the left and right branches were created recursively by `partial-tree`, each of those branches is balanced, as well, eventually resulting in a balanced tree that corresponds to the original input list.

The tree produced by `list-tree` for the list `(1 3 5 7 9 11)` is identical to the right-most tree in figure 2.16 of the text (the tree rooted at 5).

## Solution, part. B.

`list-tree`'s order of growth is determined by `partial-tree`. `partial-tree` visits each element in the original input list exactly once (it must, in order to make each element the entry of a node in the balanced tree): this is θ(*n*) operations. Each visit performs a single `cons`, which requires a constant-factor number of steps for our purposes, so the overall order of growth in steps is also θ(*n*).