[plt-scheme] a semi-trivial tree-traversal problem

From: Danny Yoo (dyoo at hkn.eecs.berkeley.edu)
Date: Tue Nov 1 18:42:54 EST 2005

On Tue, 1 Nov 2005, David Richards wrote:

> Given a nested list (a tree) of numbers, return the number that
> causes the sum of all preceding (depth-first search) numbers to be
> greater than a specified value.
> For example:
> (define L '((3 3) 2 4) )
> ; (search-width L 7)  -->  2
> ... because 3 + 3 + 2 is greater than 7.
> One solution is to flatten the list, and then walk down the list
> accumulating a total and terminating appropriately.

Hi David,

We might be able to use streams to flatten only as much as we need.  PLT
Scheme comes with a streams library in SRFI 40:


Here's rough code that may do the trick:

(module flatten-as-stream mzscheme
  (require (lib "40.ss" "srfi")) ;; streams library
  (provide flatten)

  (define (stream-append stream1 stream2)
    (if (stream-null? stream1)
        (stream-cons (stream-car stream1)
                     (stream-append (stream-cdr stream1) stream2))))

  ;; flatten: (union list datum) -> stream
  (define (flatten datum)
    (cond ((list? datum)
           (if (null? datum)
               (stream-append (flatten (car datum))
                              (flatten (cdr datum)))))
           (stream-cons datum stream-null)))))

The approach here flattens only as much as we want, and using it with
search-width then becomes really nice.  (I should reread SICP and review
streams again, just to see if there's something else I'm missing about

Hope this helps!

Posted on the users mailing list.