►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.63 Exercise 2.63

We’re comparing the following procedures for converting binaries trees into lists:

(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 '()))

The first procedure appends the list representation of the left-branch of the tree to the list formed by consing the entry of the tree with the list representation of the right-branch of the tree. This produces a list with elements sorted in ascending order from left to right. (The base case, where the tree is empty, is to return an empty list.)

The second procedure defines an inner procedure, copy-to-list, taking a tree and a list as parameters. The base case of an empty tree is the same; however, rather than returning an empty list, the given result-list argument is returned. Otherwise, it calls copy-to-list, with the first argument being the left-branch of the tree and the second being the list formed by consing the entry of the tree and the list representation of the right-branch of the tree. To create the second argument, copy-to-list is called with the right-branch of the tree and the result-list from the outer copy-to-list scope supplied as arguments.

The arguments to cons suggest that the resulting list will also be in ascending order. The two procedures visit the nodes in the same order – they just accumulate their answers in a different way. The first procedure is arguably more straightforward, by just appending results of recursive calls in a predictable order. The second procedure, however, first accumulates new results in the innermost copy-to-list call, and then uses that with cons to add the value of the current node, and then uses this with an outer copy-to-list as a result-list when working through the left side of the tree. The end result is the same, but the pipelining of data is more explicit.

We can use the trees in from figure 2.16 to verify that these procedures produce the same results:

(define ta (list 7 (list 3 (list 1 '() '()) (list 5 '() '())) (list 9 '() (list 11 '() '()))))
(define tb (list 3 (list 1 '() '()) (list 7 (list 5 '() '()) (list 9 '() (list 11 '() '())))))
(define tc (list 5 (list 3 (list 1 '() '()) '()) (list 9 (list 7 '() '()) (list 11 '() '()))))
 
(tree->list-1 ta)
 
(tree->list-2 ta)
 
(tree->list-1 tb)
 
(tree->list-2 tb)
 
(tree->list-1 tc)
 
(tree->list-2 tc)

However, although these procedures produce the same results, they do not have the same order of growth. The second procedure, visiting every node in the tree once and applying cons once per visit, is clearly O(N).

However, the first procedure calls append when visiting each node. Recall from earlier in the chapter that append is an O(N) operation. We can formalize the running time of the first procedure as a recurrence relation:

T(n) = O(n) + 2T(n/2)

This has a solution of O(nlogn).

    ← prev  up  next →