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

David Richards writes:
 > 
 > 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.

Why not just rotate the tree as you go?  No need for continuations or streams.

(define (search-width tree limit)
  (let loop ((tree tree) (sum 0))
    (if (null? tree)
	'ok
	(let ((left (car tree)) (right (cdr tree)))
	  (cond ((null? left)
		 (loop right sum))
		((pair? left)
		 (loop (cons (car left) (cons (cdr left) right)) sum))
		(else
		 (let ((sum (+ sum left)))
		   (if (> sum limit)
		       left
		       (loop right sum)))))))))

This would probably be clearer if you made a "tree" ADT (even if just
on top of lists), but I'll leave that as an exercise for the reader.

--dougo at place.org