Non-performant binary tree implementation in Clojure

binary-tree.clj

(defrecord BinaryTree [key left right]))

(defn insert [tree val]
  (if (nil? tree)
    (BinaryTree. val nil nil)
    (let [key (:key tree)]
      (cond
       (< key val) (BinaryTree. key
                                (:left tree)
                                (insert (:right tree) val))
       (> key val) (BinaryTree. key
                                (insert (:left tree) val)
                                (:right tree))))))

(defn remove [tree val]
  (let [key (:key tree)]
    (cond
     (= val key) nil
     (< key val) (BinaryTree. key
                              (:left tree)
                              (remove (:right tree) val))
     (> key val) (BinaryTree. key
                              (remove (:left tree) val)
                              (:right tree)))))

(defn contains? [tree val]
  (loop [cur-tree tree]
    (if (nil? cur-tree)
      false
      (let [key (:key cur-tree)]
        (cond
         (= key val) true
         (< key val) (recur (:right tree))
         (> key val) (recur (:left tree)))))))