Simple binary tree, implementing IPersistentCollection and IPersistentSet interfaces

tree.clj

(defn- -find
  [{:keys [left right root] :as tree} pred el acc]
  (if tree
      (if (== root el)
          [tree acc]
          (if (pred root el)
              (recur left pred el (conj acc :left))
              (recur right pred el (conj acc :right))))
      [nil acc]))

(defn- -concat-branches
  [left right]
  (if left
      (update-in left [:right] -concat-branches right)
      right))

(defn- -traverse
  [{:keys [left right root] :as tree}]
  (when tree
    (lazy-cat (-traverse left) [root] (-traverse right))))

(deftype Tree [pred tree]
  clojure.lang.Sequential

  clojure.lang.IPersistentCollection
  (seq [this]
    (-traverse tree))
  (cons [this el]
    (let [[branch trace] (-find tree pred el [])]
      (if branch
          this
          (Tree. pred (assoc-in tree (conj trace :root) el)))))
  (empty [this]
    (Tree. pred nil))
  (equiv [this tree]
    (= (seq this) (seq tree)))

  clojure.lang.IPersistentSet
  (disjoin [this el]
    (let [[{:keys [left right] :as branch} trace] (-find tree pred el [])]
      (if branch
          (Tree. pred
            (let [new-branch (-concat-branches left right)]
              (if (seq trace)
                  (assoc-in tree trace new-branch)
                  new-branch)))
          this)))
  (contains [this el]
    (-> (-find tree pred el '()) first boolean))
  (get [this el]
    (-> (-find tree pred el '()) first :root))

  clojure.lang.Counted
  (count [this]
    (count (seq this))))

(defn tree
  ([]
    (tree >))
  ([pred]
    (Tree. pred nil)))