#lang scheme

#| In the middle of making remove-bst.

   Outline:
     1. Find value to remove, work on subtree rooted there.
     2. Replace value with predecessor (in subtree) value.
        - if no predecessor, i.e. no left subtree,
         then right subtree is result of removing value.
     3. Replace predecessor node with its left subtree.
        - has no right subtree, since predecessor.
        - to "replace", link subtree into node's parent.

|#

#| Remove and return the maximum from non-empty bst t. |#
(define remove-max
  (lambda (t parent)
    (if (bst-right t)
        (remove-max (bst-right t) t)
        ???)))

#| 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]
          [else ; at value to remove
           ; if no predecessor of v in t
           ;   the right subtree of t is t without v
           (if (not (bst-left t)) (bst-right t)
               ; else
               ;   get its immediate predecessor node
               ;     go left, then all the way right
               (remove-max (bst-left t) (bst-right (bst-left t)))