Immutable and persistent Binary Tree

binary-tree.clj

(defrecord Node [value left right])

(defn create [value]
  (Node. value nil nil))

(defn insert [{:keys [left right value] :as tree} v]
  (if tree
    (cond
     (< v value) (Node. value (insert left v) right)
     (> v value) (Node. value left (insert right v))
     :else (Node. v left right))
    (create v)))

(defn remove [{:keys [left right value] :as tree} v]
  (cond
   (< v value) (Node. value (remove left v) right)
   (> v value) (Node. value left (remove right v))
   :else nil))

(defn contains [{:keys [left right value] :as tree} v]
  (if tree
    (cond
     (< v value) (contains left v)
     (> v value) (contains right v)
     :else true)
    false))

(def btree
  (-> (create 1)
      (insert 2)
      (insert 3)
      (insert -2)
      (remove -2)))

(contains btree -2)
;=> false