SICP Exercise 2.66

sicp

Question

Implement the lookup procedure for the case where the set of records is structured as a binary tree, order by the numerical values of the keys.

Answer

(define (lookup given-key tree-of-records)
  (cond ((null? tree-of-records) false)
        ((equal? given-key (key (entry tree-of-records)))
         (entry tree-of-records))
        ((< given-key (key (entry tree-of-records)))
         (lookup given-key (left-branch tree-of-records)))
        ((> given-key (key (entry tree-of-records)))
         (lookup given-key (right-branch tree-of-records)))))

We can’t really test this yet without a representation for key.