# [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 Previous message: [plt-scheme] a semi-trivial tree-traversal problem Next message: [plt-scheme] a semi-trivial tree-traversal problem Messages sorted by: [date] [thread] [subject] [author]

```
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!

```

 Posted on the users mailing list. Previous message: [plt-scheme] a semi-trivial tree-traversal problem Next message: [plt-scheme] a semi-trivial tree-traversal problem Messages sorted by: [date] [thread] [subject] [author]