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

David Richards wrote:
>*
*>* 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.
*...
>* 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?
*
How about:
(define (search-width tree limit)
(let/ec return
(define (search tree limit sum)
(cond
[(null? tree) sum]
[(number? tree) (if (> (+ sum tree) limit)
(return tree)
(+ sum tree))]
[else (foldl (lambda (t sum)
(search t limit sum))
sum
tree)]))
(search tree limit 0)
"not found"))
(do ([i 46 (- i 1)]
[l '() (cons (search-width '(((1 2) 3 (4 5)) 6 7 (8 9)) i) l)])
((< i 0) l))
--
Jens Axel Søgaard