# sicp-ex-2.35

Using recursion, it's possible to do it with map and without enumerate-tree the following way.

```
(define (count-leaves-recursive t)
(accumulate + 0 (map (lambda (node)
(if (pair? node)
(count-leaves-recursive node)
1))
t)))

;; Usage
(count-leaves-recursive tree) ;; => 7
```

The previous solution counts the empty list as a leaf:

``` (count-leaves-recursive (quote (1 () () (() ()) () () 2)))
;; Value: 8
```

This can easily be remedied by using more conditions:

``` (define (count-leaves-recursive t)
(accumulate + 0
(map
(lambda (t)
(cond ((null? t) 0)
((pair? t) (count-leaves-recursive t))
(else 1)))
t)))

;; which gives
(count-leaves-recursive '(1 2 () () (3 () ())))
;; Value: 3
```

For those who are confused about how the above is working consider the following example:

Having the following tree:

``` (define tree (list 1 2 (list 3 4) (list 5 (list 6 7))))
(count-leaves-recursive tree) ;; => 7
```

The map call in the function would flatten the tree into a list of the top level nodes with each one containing the count of its children nodes, if the node in it self is not a tree then 1 would be returned from the iterator passed to the map call.

Yielding (list 1 1 2 3) Which would be passed to the accumulator and a simple summation would be made.

The following illustrates the mapping on the tree, numbers would map to one and lists would map to its sum:

```                            7
^
|
(1              1              2                     3)
|              |              |                     |
1              2             (1 1)              (1    2)
| |                |    |
3 4                5  (1 1)
| |
6 7
```

My solution is a "tomato-tomato" of above.

Identity-mapping and using recursion in proc.

``` (define (count-leaves t)
(define proc (lambda (x y) (if (pair? x) (+ (count-leaves x) y)
(+ 1 y))))
(define init_val 0)
(define seq (map (lambda (a) a) t))
(accumulate proc init_val seq))
```

jz

I couldn't figure out a way of doing this with map without relying on the previously-defined enumerate-tree. enumerate-tree is used a lot in the chapter so it's probably what's intended.

```
;; Accumulates the result of the first and the already-accumulated
;; rest.
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
(accumulate cons nil (list 2 3 4 5 6))

;; Pulls out all the leaves of the tree, returns as a flat list.
(define (enumerate-tree tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))

(define (count-leaves t)
(accumulate +
0
(map (lambda (x) 1)
(enumerate-tree t))))

;; Usage
(define tree (list 1 2 3 (list 4 5 (list 6 7))))
(count-leaves tree)  ;; => 7

```

If we remove the constraint (aka hint) of using map, we can do it without enumerate-tree, but we have to make a recursive call to count-leaves if the current node is another subtree, since accumulate can't descend into the subtrees.

```
(define (count-leaves-without-map t)
(accumulate (lambda (node count-thus-far)
(+ count-thus-far
(cond ((null? node) 0)
((not (pair? node)) 1)
(else
(count-leaves-without-map node)))))
0
t))

;; Usage
(count-leaves-without-map tree) ;; => 7

```

revc

A different version of the procedure uses enumerate-tree, just like jz, but with a slight difference

```
(define (count-leaves t)
(accumulate (lambda (x y) (+ (length x) y)) 0 (map enumerate-tree t)))

```

Rather Iffy

```
(define (count-leaves t)
(accumulate +  0 (map (lambda(x) 1)  (enumerate-tree t))))

```