Lecture overview -- Keyboard shortcut: 'u'  Previous page: Practical example: Length of an improper list -- Keyboard shortcut: 'p'    Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home    Lecture 3 - Page 42 : 42
Functional Programming in Scheme
Name binding, Recursion, Iteration, and Continuations
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 out of the tree traversal

(define (find-in-tree tree pred)
  (lambda (found)
       (lambda (tree pred)
            (if (pred tree)
                (found tree)
                (let ((subtrees (subtree-list tree)))
                      (lambda (subtree) (find-in-tree1 subtree pred))
    (find-in-tree1 tree pred)))  ))

A tree search function which uses a continuation found if we find what we search for. Notice that this examples requires the function subtree-list, in order to work. The function returns #f in case we do not find node we are looking for. Notice that it makes sense in this example to have both the if expression and the #f value in sequence!