; lowest common ancestor

(define (tree k l r) (vector k l r))
(define (key t) (vector-ref t 0))
(define (lkid t) (vector-ref t 1))
(define (rkid t) (vector-ref t 2))
(define nil (vector 'nil 'nil 'nil))
(define (nil? t) (eq? t nil))

(define (lookup lt? t k)
  (cond ((nil? t) #f)
        ((lt? k (key t)) (lookup lt? (lkid t) k))
        ((lt? (key t) k) (lookup lt? (rkid t) k))
        (else #t)))

(define (insert lt? t k)
  (cond ((nil? t) (tree k nil nil))
        ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t)))
        ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k)))
        (else (tree k (lkid t) (rkid t)))))

(define (lca lt? t lo hi)
  (cond ((and (not (lt? (key t) lo))
              (not (lt? hi (key t)))) (key t))
        ((lt? (key t) lo) (lca lt? (rkid t) lo hi))
        (else (lca lt? (lkid t) lo hi))))

(define t nil)
(set! t (insert < t 8))
(set! t (insert < t 3))
(set! t (insert < t 10))
(set! t (insert < t 1))
(set! t (insert < t 6))
(set! t (insert < t 14))
(set! t (insert < t 4))
(set! t (insert < t 7))
(set! t (insert < t 13))

(display (lca < t 4  7)) (newline) ; 6
(display (lca < t 4 10)) (newline) ; 8
(display (lca < t 1  4)) (newline) ; 3
(display (lca < t 1  3)) (newline) ; 3
(display (lca < t 3  6)) (newline) ; 3

6
8
3
3
3