]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex2_64.clj
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex2_64.clj
1 (ns sicp.ex2_64
2   (:use [sicp.ch2_3 :only (make-tree)]))
3
4 (declare partial-tree)
5
6 (defn list->tree [elements]
7   (first (partial-tree elements (count elements))))
8
9 (defn partial-tree [elts n]
10   (if (= n 0)
11     (cons '() elts)
12     (let [left-size     (quot (- n 1) 2)
13           left-result   (partial-tree elts left-size)
14           left-tree     (first left-result)
15           non-left-elts (rest left-result)
16           right-size    (- n (+ left-size 1))
17           this-entry    (first non-left-elts)
18           right-result  (partial-tree (rest non-left-elts) right-size)
19           right-tree    (first right-result)
20           remaining-elts (rest right-result)]
21       (cons (make-tree this-entry
22                        left-tree
23                        right-tree)
24             remaining-elts))))
25
26 (comment
27   "partial-tree divides the input sequence roughly into 2 halfs and creates a tree of
28    partial-trees on each of the branches."
29   "The tree for the input '(1 3 5 7 9 11) looks like this:"
30   "
31           5
32         /   \\r
33        1     9
34         \   / \\r
35          3 7   11
36   "
37   "partial-tree does a cons for every element of the list. So, order of growth is O(n)."
38 )