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

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Tue Nov 1 18:22:44 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]

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

```

 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]