A BST implementation in Clojure


My new workplace is heavily invested in Clojure, and while other languages are used as the need arises (Golang, Elixir, Haskell, PureScript, TypeScript just to name a few), it is primarily a Clojure shop.

This was rather interesting for me since I have dabbled with Common Lisp, and on the surface, a lot of the basic concepts immediately carried over (especially macros, with minor syntactic differences and the hygienic aspects of Clojure macros). That being said, a lot of the core concepts/philosophies/approaches are rather different, and that’s where dabbling with Haskell was probably more useful in me getting up to speed on those concepts.

I’m enjoying learning it so far, but I believe that real learning (especially learning how to write idiomatic Clojure) will happen only when I start doing real projects.

Nevertheless, it has been fun playing around on the REPL (even though CIDER is no SLIME), and I thought of posting a small BST example that I did for fun – the traversals are especially inspired by the samples in “Joy of Clojure” (a really good book in my opinion, barring the chapter on macros which I thought as atrocious).

Without any further ceremony, here is the code:

(ns bst)

;;;
;;; define the node type
;;;

(defrecord BSTNode [data left right])

;;;
;;; define the operations on the bst
;;;

(defn bst-add [root data]
  "adds a new node to the tree - creating the root node if the root is nil"
  (cond
    (nil? root) (BSTNode. data nil nil)
    (<= data (:data root)) (BSTNode. (:data root) (bst-add (:left root) data) (:right root))
    :else (BSTNode. (:data root) (:left root) (bst-add (:right root) data))))

(defn bst-size [root]
  "returns the number of nodes in the BST"
  (cond
    (nil? root) 0
    :else (+ 1 (bst-size (:left root)) (bst-size (:right root)))))

(defn bst-height [root]
  "returns the height of the BST"
  (cond
    (nil? root) 0
    :else (inc (max (bst-height (:left root)) (bst-height (:right root))))))

(defn bst-preorder [root]
  "returns the nodes of the BST traversing in pre-order fashion"
  (when root
    (concat [(:data root)] (bst-preorder (:left root)) (bst-preorder (:right root)))))

(defn bst-inorder [root]
  "returns the nodes of the BST traversing in in-order fashion"
  (when root
    (concat (bst-inorder (:left root)) [(:data root)] (bst-inorder (:right root)))))

(defn bst-postorder [root]
  "returns the nodes of the BST traversing in post-order fashion"
  (when root
    (concat (bst-postorder (:left root)) (bst-postorder (:right root)) [(:data root)]))) 

;;;
;;; sample randomized BST
;;;
(def my-bst (reduce bst-add nil (for [_ (range (+ (rand-int 20) 10))] (rand-int 100))))

(printf "size = %d, height = %d\n" (bst-size my-bst) (bst-height my-bst))

(println "pre-order: " (bst-preorder my-bst))

(println "in-order: " (bst-inorder my-bst))

(println "post-order: " (bst-postorder my-bst))

And here is a small run-through on the REPL (I thought using Leiningen would be overkill for such a small “project”):

user> (load-file "bst.clj")
size = 15, height = 6
pre-order:  (42 9 3 18 13 31 28 30 33 38 75 56 56 92 92)
in-order:  (3 9 13 18 28 30 31 33 38 42 56 56 75 92 92)
post-order:  (3 13 30 28 38 33 31 18 9 56 56 92 92 75 42)
nil
user> (in-ns 'bst)
#namespace[bst]
bst> my-bst
#bst.BSTNode{:data 42, :left #bst.BSTNode{:data 9, :left #bst.BSTNode{:data 3, :left nil, :right nil}, :right #bst.BSTNode{:data 18, :left #bst.BSTNode{:data 13, :left nil, :right nil}, :right #bst.BSTNode{:data 31, :left #bst.BSTNode{:data 28, :left nil, :right #bst.BSTNode{:data 30, :left nil, :right nil}}, :right #bst.BSTNode{:data 33, :left nil, :right #bst.BSTNode{:data 38, :left nil, :right nil}}}}}, :right #bst.BSTNode{:data 75, :left #bst.BSTNode{:data 56, :left #bst.BSTNode{:data 56, :left nil, :right nil}, :right nil}, :right #bst.BSTNode{:data 92, :left #bst.BSTNode{:data 92, :left nil, :right nil}, :right nil}}}

Enjoyable, but there’s still the most interesting bits of Clojure to come in this learning path – concurrency and designing programs the idiomatic way!

Advertisements

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s