bst.clj

(ns bst)

(def blank-bst
  {:left nil
   :right nil
   :value nil})

(defn make-bst [val]
  (assoc blank-bst :value val))

(defn add-to-bst [bst val]
  (cond (nil? bst)           (make-bst val)
        (< val (:value bst)) (assoc bst :left (add-to-bst (:left bst) val))
        :else                (assoc bst :right (add-to-bst (:right bst) val))))

(defn leftmost [bst]
  (if (nil? (:left bst))
    bst
    (leftmost (:left bst))))

(defn rightmost [bst]
  (if (nil? (:right bst))
    bst
    (rightmost (:right bst))))

(defn find-in-bst [bst val]
  (cond (< val (:value bst)) (recur (:left bst) val)
        (> val (:value bst)) (recur (:right bst) val)
        (= val (:value bst)) bst
        :else                nil))

(defn assoc-bst [bst replace-node val]
  (cond (< val (:value bst)) ;left
        (assoc bst :left (assoc-bst (:left bst) replace-node val)),
        (> val (:value bst)) ;right
        (assoc bst :right (assoc-bst (:right bst) replace-node val)),
        (= val (:value bst))
        replace-node,
        :else
        nil))

(defn swap-delete [swap-node]
  ;we only call this if we know there's either a left or right child, so:
  (let [other-node    (if (not (nil? (:left swap-node)))
                        (rightmost (:left swap-node))
                        (leftmost (:right swap-node)))
        other-val     (:value other-node)
        deleted-other (assoc-bst swap-node nil other-val)]
    (assoc deleted-other :value other-val)))

(defn delete-from-bst [bst val]
  (let [delete-node (find-in-bst bst val)]
    (if (and (nil? (:left delete-node))
             (nil? (:right delete-node))) ;no children
      (assoc-bst bst nil val)
      (assoc-bst bst (swap-delete delete-node) val)
      )
    ))