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

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:
http://srfi.schemers.org/srfi-40/srfi-40.html
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)
stream2
(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-null
(stream-append (flatten (car datum))
(flatten (cdr datum)))))
(else
(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
this.)
Hope this helps!