Binary tree naive impl.

a.clj

(ns a)

(defrecord Tree [node-value left-tree right-tree])

(defn insert [tree new-value]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (cond
      (nil? node-value) (Tree. new-value nil nil)
      (< new-value node-value) (Tree. node-value (insert left-tree new-value) right-tree)
      (> new-value node-value) (Tree. node-value left-tree (insert right-tree new-value))
      :else tree)))

(defn find-min [tree]
  (let [{:keys [node-value left-tree]} tree]
    (if left-tree
      (recur left-tree)
      node-value)))

(defn find-max [tree]
  (let [{:keys [node-value right-tree]} tree]
    (if right-tree
      (recur right-tree)
      node-value)))

(defn delete [tree some-value]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (cond
      (< some-value node-value) (Tree. node-value (delete left-tree some-value) right-tree)
      (> some-value node-value) (Tree. node-value left-tree (delete right-tree some-value))
      (nil? left-tree) right-tree
      (nil? right-tree) left-tree
      :else (let [min-value (find-min right-tree)]
              (Tree. min-value left-tree (delete right-tree min-value))))))

(defn contains-value? [tree some-value]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (cond
      (nil? tree) false
      (< some-value node-value) (recur left-tree some-value)
      (> some-value node-value) (recur right-tree some-value)
      (= some-value node-value) true
      :else false)))
      
      
(defn traversal-tree-post-order [tree apply-fn]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (when tree
      (traversal-tree left-tree apply-fn)
      (traversal-tree right-tree apply-fn)
      (apply-fn node-value))))  


(defn traversal-tree-in-order [tree apply-fn]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (when tree
      (traversal-tree left-tree apply-fn)
      (apply-fn node-value)
      (traversal-tree right-tree apply-fn))))


(defn traversal-tree-pre-order [tree apply-fn]
  (let [{:keys [node-value left-tree right-tree]} tree]
    (when tree
      (apply-fn node-value)
      (traversal-tree left-tree apply-fn)
      (traversal-tree right-tree apply-fn))))
      

(defn count-tree [tree]
  (let [{:keys [left-tree right-tree]} tree]
    (if tree
      (+ 1 (count-tree left-tree) (count-tree right-tree))
      0)))

(defn height-tree
  ([tree] (height-tree tree 0))
  ([tree current-height]
   (let [{:keys [left-tree right-tree]} tree]
     (if tree
       (max (height-tree left-tree (inc current-height))
            (height-tree right-tree (inc current-height)))
       current-height))))

(defn into-tree
  [coll]
  (reduce insert nil coll))



(comment

  (def t1 (insert nil 8))
  (count-tree t1)
  (height-tree t1)

  (def t2 (into-tree [8 6 4 5 2 9 12 11 10]))

  (count-tree t2)
  (height-tree t2)
  (clojure.pprint/pprint t2)

  (height-tree (:left-tree t2))
  (height-tree (:right-tree t2))
  
  (traversal-tree-post-order t2 prn)

  )