2 (:use [sicp.ch2_3 :only (entry left-branch right-branch)]
5 (defn tree->list-1 [tree]
8 (concat (tree->list-1 (left-branch tree))
10 (tree->list-1 (right-branch tree))))))
12 (defn tree->list-2 [tree]
13 (let [copy-to-list (fn f [tree result-list]
18 (f (right-branch tree) result-list)))))]
19 (copy-to-list tree '())))
21 (deftest test-for-some-trees
23 (tree->list-1 '(7 (3 (1 ()) (5 ())) (9 () (11 ())))) '(1 3 5 7 9 11)
24 (tree->list-2 '(7 (3 (1 ()) (5 ())) (9 () (11 ())))) '(1 3 5 7 9 11)
25 (tree->list-1 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))) '(1 3 5 7 9 11)
26 (tree->list-2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ()))))) '(1 3 5 7 9 11)
27 (tree->list-1 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))) '(1 3 5 7 9 11)
28 (tree->list-2 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))) '(1 3 5 7 9 11)))
32 "yes, as the above tests show, they add elements into the list in the same order
33 and hence produce same lists."
38 "tree->list-1 does a cons and an append of two lists at every step. The depth of the
39 tree is log(n). append grows as length of the list. The number of steps required to
40 traverse down to the tree is log(n). So, this is a O(n.log(n)) operation."
42 "list->tree-2 does only a cons operation at every step. So this is a O(n) operation."