#lang scheme

[define-struct bst [left value right] #:mutable]

#| For a bst t, print out the values in t and its subtrees in order,
    one per line. |#
[define display-bst
  [lambda [t]
    [when t
      [display-bst [bst-left t]]
      [newline] [display [bst-value t]]
      [display-bst [bst-right t]]]]]

#| For a number v and bst t holding numbers, where v is not in t,
    inserts v into t and returns the updated t |#
[define insert-bst
  [lambda [v t]
    [if t
        [begin ; multiple statements, for side-effects, last value returned
          [if [< v [bst-value t]]
              [set-bst-left! t [insert-bst v [bst-left t]]]
              [set-bst-right! t [insert-bst v [bst-right t]]]]
          t]                
        [make-bst #f v #f]]]]

#| Remove and return the maximum from non-empty bst parent having
    non-empty child on right. |#
(define remove-max
  (lambda (parent child)
    (if (bst-right child) ; nothing guarantees child is not #f
        (remove-max child (bst-right child))
        ; child is immediate predecessor
        ; return its value
        ; link its left to right of parent
        (begin
          (set-bst-right! parent (bst-left child))
          (bst-value child)))))

#| For a number v and bst t holding numbers, where v is in t,
    removes v from t and returns the updated t |#
(define remove-bst
  (lambda (v t)
    (cond [(< v (bst-value t)) (set-bst-left! t (remove-bst v (bst-left t)))
                               t]
          [(> v (bst-value t)) (set-bst-right! t (remove-bst v (bst-right t)))
                               t]
          ; Now at the value to remove.
          [(not (bst-left t)) (bst-right t)] ; no immediate predecessor under t
          [(not (bst-right (bst-left t))) ; immediate predecessor immediately left
           (set-bst-value! t (bst-value (bst-left t)))
           (set-bst-left! t (bst-left (bst-left t)))
           t]
          [else
           (set-bst-value! t (remove-max (bst-left t) (bst-right (bst-left t))))
           t])))

(define list->bst
  (lambda (t l)
    (if (empty? l) t
        (list->bst (insert-bst (first l) t) (rest l)))))

(display-bst
 ; Immediate predecessor underneath but not immediately left
 (remove-bst 5
             (list->bst #f '(5 2 1 4 3 6))))
(display-bst
 ; Immediate predecessor immediately left
 (remove-bst 5
             (list->bst #f '(5 2 1 6))))
(display-bst
 ; No immediate predecessor underneath
 (remove-bst 5
             (list->bst #f '(5 6))))