Practical example: Searching a binary tree

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'

Annotated slide -- Keyboard shortcut: 't'

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

Coroutines

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