#lang racket
 
(define (list->bst lst (cmp <) #:key (fn identity))
  (define (loop lst cmp fn)
    (if (null? lst)
        '()
        (let ((pivot (car (drop lst (quotient (length lst) 2)))))
          (let ((left (loop (filter (lambda (x)
                                      (cmp (fn x) (fn pivot)))
                                    lst) cmp fn))
                (right (loop (filter (lambda (x)
                                       (cmp (fn pivot) (fn x)))
                                     lst) cmp fn)))
            (cond ((list? pivot) `(,@pivot ,left ,right))
                  ((pair? pivot) (match-let (((cons k v) pivot))
                                   `(,k ,v ,left ,right)))
                  (else `(,pivot ,left ,right)))))))
  (loop (sort lst cmp #:key fn) cmp fn))
 
(define (bst-search v tree (cmp equal?) #:keyfn (kfn <) #:key (fn car))
  (match tree
    ('() #f)
    (`(,lvp ... ,left ,right)
     (cond ((cmp v (fn lvp)) lvp)
           ((kfn v (fn lvp)) (bst-search v left cmp #:keyfn kfn #:key fn))
           (else (bst-search v right cmp #:keyfn kfn #:key fn))))))

I2xhbmcgcmFja2V0CgooZGVmaW5lIChsaXN0LT5ic3QgbHN0IChjbXAgPCkgIzprZXkgKGZuIGlkZW50aXR5KSkKICAoZGVmaW5lIChsb29wIGxzdCBjbXAgZm4pCiAgICAoaWYgKG51bGw/IGxzdCkKICAgICAgICAnKCkKICAgICAgICAobGV0ICgocGl2b3QgKGNhciAoZHJvcCBsc3QgKHF1b3RpZW50IChsZW5ndGggbHN0KSAyKSkpKSkKICAgICAgICAgIChsZXQgKChsZWZ0IChsb29wIChmaWx0ZXIgKGxhbWJkYSAoeCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoY21wIChmbiB4KSAoZm4gcGl2b3QpKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbHN0KSBjbXAgZm4pKQogICAgICAgICAgICAgICAgKHJpZ2h0IChsb29wIChmaWx0ZXIgKGxhbWJkYSAoeCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKGNtcCAoZm4gcGl2b3QpIChmbiB4KSkpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsc3QpIGNtcCBmbikpKQogICAgICAgICAgICAoY29uZCAoKGxpc3Q/IHBpdm90KSBgKCxAcGl2b3QgLGxlZnQgLHJpZ2h0KSkKICAgICAgICAgICAgICAgICAgKChwYWlyPyBwaXZvdCkgKG1hdGNoLWxldCAoKChjb25zIGsgdikgcGl2b3QpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGAoLGsgLHYgLGxlZnQgLHJpZ2h0KSkpCiAgICAgICAgICAgICAgICAgIChlbHNlIGAoLHBpdm90ICxsZWZ0ICxyaWdodCkpKSkpKSkKICAobG9vcCAoc29ydCBsc3QgY21wICM6a2V5IGZuKSBjbXAgZm4pKQoKKGRlZmluZSAoYnN0LXNlYXJjaCB2IHRyZWUgKGNtcCBlcXVhbD8pICM6a2V5Zm4gKGtmbiA8KSAjOmtleSAoZm4gY2FyKSkKICAobWF0Y2ggdHJlZQogICAgKCcoKSAjZikKICAgIChgKCxsdnAgLi4uICxsZWZ0ICxyaWdodCkKICAgICAoY29uZCAoKGNtcCB2IChmbiBsdnApKSBsdnApCiAgICAgICAgICAgKChrZm4gdiAoZm4gbHZwKSkgKGJzdC1zZWFyY2ggdiBsZWZ0IGNtcCAjOmtleWZuIGtmbiAjOmtleSBmbikpCiAgICAgICAgICAgKGVsc2UgKGJzdC1zZWFyY2ggdiByaWdodCBjbXAgIzprZXlmbiBrZm4gIzprZXkgZm4pKSkpKSk=