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

From: David Richards (dirichards at cox.net)
Date: Tue Nov 1 17:42:56 EST 2005

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.