Lecture overview -- Keyboard shortcut: 'u'  Previous page: Practical example: Length of an improper list -- Keyboard shortcut: 'p'  Next page: Continuation Passing Style [Section] -- Keyboard shortcut: 'n'  Lecture notes - all slides together  Annotated slide -- Keyboard shortcut: 't'  Alphabetic index  Help page about these notes  Course home    Simulation of other Paradigms and Continuations - slide 31 : 43

Practical example: Searching a binary tree

Searching a binary tree involves a recursively defined tree traversal.

If we find the node we are looking for it is convenient to throw the node out of the tree traversal.

Notice the slightly 'imperative style' in find-in-tree below.

(define (find-in-tree tree pred)
 (call-with-current-continuation
  (lambda (found)
   (letrec
    ((find-in-tree1
       (lambda (tree pred)
            (if (pred tree)
                (found tree)
                (let ((subtrees (subtree-list tree)))
                   (for-each
                      (lambda (subtree) (find-in-tree1 subtree pred))
                      subtrees)))
            #f)))
    (find-in-tree1 tree pred)))  ))

We will see more examples of continuation programming in the lecture about 'Simulation of Other Paradigms in Scheme': Coroutines