Practical example: Searching a binary tree

Lecture overview -- Keyboard shortcut: 'u'

Previous page: Practical example: Length of an improper list -- Keyboard shortcut: 'p'

Lecture notes - all slides and notes together

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

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!