; binary search tree: in-order predecessor and successor

(define (tree key lkid rkid) (vector key lkid rkid))

(define (key tree) (vector-ref tree 0))
(define (lkid tree) (vector-ref tree 1))
(define (rkid tree) (vector-ref tree 2))

(define nil (vector 'nil 'nil 'nil))
(vector-set! nil 1 nil)
(vector-set! nil 2 nil)
(define (nil? tree) (eqv? tree nil))

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

(define (minimum t)
  (cond ((nil? t) #f)
        ((nil? (lkid t)) (key t))
        (else (minimum (lkid t)))))

(define (maximum t)
  (cond ((nil? t) #f)
        ((nil? (rkid t)) (key t))
        (else (maximum (rkid t)))))

(define (pred lt? t k)
  (define (return t) (if (nil? t) #f (key t)))
  (let loop ((t t) (prev nil))
    (cond ((nil? t) (return prev))
          ((lt? (key t) k) (loop (rkid t) t))
          ((lt? k (key t)) (loop (lkid t) prev))
          ((nil? (lkid t)) (return prev))
          (else (maximum (lkid t))))))

(define (succ lt? t k)
  (define (return t) (if (nil? t) #f (key t)))
  (let loop ((t t) (next nil))
    (cond ((nil? t) (return next))
          ((lt? k (key t)) (loop (lkid t) t))
          ((lt? (key t) k) (loop (rkid t) next))
          ((nil? (rkid t)) (return next))
          (else (minimum (rkid t))))))

(define t nil)
(set! t (insert < t 3))
(set! t (insert < t 9))
(set! t (insert < t 4))
(set! t (insert < t 1))
(set! t (insert < t 7))
(set! t (insert < t 8))
(set! t (insert < t 2))
(set! t (insert < t 6))

(display t) (newline)
(display (minimum t)) (newline)
(display (maximum t)) (newline)

(display (succ < t 0)) (newline)
(display (succ < t 1)) (newline)
(display (succ < t 2)) (newline)
(display (succ < t 3)) (newline)
(display (succ < t 4)) (newline)
(display (succ < t 5)) (newline)
(display (succ < t 6)) (newline)
(display (succ < t 7)) (newline)
(display (succ < t 8)) (newline)
(display (succ < t 9)) (newline)
(display (succ < t 10)) (newline)

(display (pred < t 10)) (newline)
(display (pred < t 9)) (newline)
(display (pred < t 8)) (newline)
(display (pred < t 7)) (newline)
(display (pred < t 6)) (newline)
(display (pred < t 5)) (newline)
(display (pred < t 4)) (newline)
(display (pred < t 3)) (newline)
(display (pred < t 2)) (newline)
(display (pred < t 1)) (newline)
(display (pred < t 0)) (newline)

#(3 #(1 #0=#(nil #0# #0#) #(2 #0# #0#)) #(9 #(4 #0# #(7 #(6 #0# #0#) #(8 #0# #0#))) #0#))
1
9
1
2
3
4
6
6
7
8
9
#f
#f
9
8
7
6
4
4
3
2
1
#f
#f