Skip to content

Instantly share code, notes, and snippets.

@omnisis omnisis/gist:1625035
Created Jan 17, 2012

Embed
What would you like to do?
Basic Binary Tree with test sample in Clojure
;; binary tree using defrecord (as oppossed to maps)
(defrecord TreeNode [val l r])
;; constructor method: creates a new tree
(defn make-tree [root]
(TreeNode. root nil nil))
;; creates a new binary tree by appending v to existing tree
(defn tree-append [t v]
(cond
(nil? t) (TreeNode. v nil nil)
(< v (:val t)) (TreeNode. (:val t) (tree-append (:l t) v) (:r t))
:else (TreeNode. (:val t) (:l t) (tree-append (:r t) v))))
;; in-order traversal of binary tree
(defn traverse-in-order [t]
(when t
(concat (traverse-in-order (:l t)) [(:val t)] (traverse-in-order (:r t)))))
;; tests
(def sample-tree (make-tree 1))
(def sample-tree (reduce tree-append sample-tree [3 5 2 4 6])) ;; show appending to new tree
(traverse-in-order sample-tree) ;; show traversal
(traverse-in-order (tree-append sample-tree 45)) ;; show traversing after appending
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.