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

 From: David Richards (dirichards at cox.net) Date: Tue Nov 1 17:42:56 EST 2005 Next message: [plt-scheme] a semi-trivial tree-traversal problem Messages sorted by: [date] [thread] [subject] [author]

```Here is a semi-trivial tree-traversal problem.

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.  But that
solution requires that the flatten operation be executed first, on a
tree of indeterminate and potentially massive size.  A potentially
wasteful process.

So, here is a potential solution that I hammered out.

(define (search-width L offset)
(call-with-current-continuation
(lambda (return)
(letrec ((_search-width (lambda (L)
(if (list? L)
(if (empty? L)
#f
(let ()
(_search-width (car L))
(_search-width (cdr L))
#f))
(if (> L offset)
(return L)
(let ()
(set! offset (- offset L))
#f))))))
(_search-width L)))))

As far as I can determine, this works.  But I have some questions.
First, does this style of programming lead to any 'hidden' problems?
Second, how might we eliminate the 'ugly' call to set! ?  And
finally, is there a generally better approach to solving this
problem, either in terms of efficiency, or coding style?

David Richards

```

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