SICP exercise 2.28 - counting leaves in a tree (recursive process)

Question

From SICP

Exercise 2.28: Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

After writing this code, I found out that implementing this in an iterative way is easier and more straight forward. But I ended up implementing this in a more complicated way. I'd like to think this is a recursive process. The argument "remaining" is not an accumulator. It stores all remaining items that are not yet consed into the new list.

Please review my code.

(define (fringe tree)
    (define (aux lst remaining)
        (cond
            ((null? lst)
                (if (null? remaining)
                    '()
                    (aux remaining '())))
            ((pair? (car lst)) (aux (car lst) (aux (cdr lst) remaining)))
        (else (cons (car lst) (aux (cdr lst) remaining)))))
    (aux tree '()))

• How does it compare to the iterative version I linked to above?
• What is the order of growth of my function? Is it O(N)?
• How can it be faster?
• If I used append rather than cons, would it slow my function a lot?
• How can I improve this code?

Answer 1

How does it compare to the iterative version I linked to above?

I actually don't see any iterative versions, all of the examples call themselves twice in the main recursive logic. (as far as I can tell)

What is the order of growth of my function? Is it O(N)?

The best case as for time in any complete tree traversal is O(N log(N)) as is yours. The big problem is that it's memory overhead is O(N)

How can it be faster?

Memory overhead can be kept to O(log(N))

If I used append rather than cons, would it slow my function a lot?

Looking through the examples, append is used mainly to keep the double-recursive call in the same order as input. Notice with yours (aux remaining '()))) that you flip the remaining to lst. when you hit the bottom of the tree. Using append on average will cause a O(N log(N)) delay.

How can I improve this code?

Using an ADT would help readibility. empty-tree? instead of null? - left instead of car, right instead of cdr.

Don't recur twice at the same time call e.g. (append (recur left) (recur right))

(define (leaf? tree)
   (not (pair? tree)))
(define (left tree) 
   (car tree))
(define (right tree)
   (cadr tree))

(define (fringe tree)
  (define (fringe-helper tree acc)
    (if (leaf? tree)
        (cons tree acc)
        (let ((right-fringes
                  (fringe-helper (right tree) acc)))
           (fringe-helper (left tree) right-fringes))))
 (fringe-helper tree '()))

This evaluates right-fringes first, That way at most you have at most log(n) number of fringe-helpers on the stack waiting for a return. It's the same as the second try in your link, with some abstract procedures instead of directly using null? pair? etc.