# sicp-ex-2.66

x3v

binary trees are fast af

``` ;; returns false if key not in records, else key
(define (lookup given-key set-of-records)
(if (null? set-of-records) #f
(let ((parent (entry set-of-records)))
(cond ((eq? parent '()) #f)
((= given-key parent) parent)
(else
(lookup given-key
(if (< given-key parent)
(left-branch set-of-records)
(right-branch set-of-records))))))))
```

My implementation shares the same basic ideas with meteorgan's.

Based on the book adjoin-set definition, only branches of leaf can be nil. Based on left-branch,right-branch definition, they will just extract nil. So (eq? parent '()) can't occur.

meteorgan

The solution is similar to element-of-set?

``` (define (lookup given-key set-of-records)
(cond ((null? set-of-records) #f)
((= given-key (key (entry set-of-records)))
(entry set-of-records))
((< given-key (key (entry set-of-records)))
(lookup given-key (left-branch set-of-records)))
(else (lookup given-key (right-branch set-of-records)))))
```

``` (define (lookup given-key set-of-records)
(if (null? set-of-records)
false
(let ((node-entry (entry set-of-records)))
(let ((node-key (key node-entry)))
(if (= given-key node-key)
node-entry
(lookup given-key
((if (< given-key node-key) left-branch right-branch) set-of-records)))))))
```

chessweb

A record looks like this: ((key value) left-branch right-branch)

``` (define (lookup given-key set-of-records)
(cond
((null? set-of-records)
#f)
((= given-key (entry (car (set-of-records))))
(cadar set-of-records)) ; evaluates to value
((< given-key (entry (car (set-of-records))))
(lookup given-key (left-branch set-of-records)))
((> given-key (entry (car (set-of-records))))
(lookup given-key (right-branch set-of-records)))))
```