Implementing a binary search tree in clojure

Question

I am trying to become familiar with Clojure and so I've started to implement some basic algorithm and data structures. I currently have a problem with implementing a binary search tree. Here is my code:

(defstruct bst :left :right :key)

(defn add-bst [n bst-t]
  (cond
    (nil? bst-t) (struct-map bst :left nil :right nil :key n)
    (< n (:key bst-t))  (struct-map bst :left (add-bst n (:left bst-t))
                                :right (:right bst-t) :key (:key bst-t))
    (> n (:key bst-t))  (struct-map bst :left (:left bst-t)
                                :right (add-bst n (:right bst-t)) :key (:key bst-t))
    true bst-t))

I was trying to add random number into BST in the REPL, line so:

(exercise.new-ns/add-bst 5 nil)

But I get a NullPointerException, but I don't understand why I am getting this exception. Is there something wrong with my code?

If you are using at least Clojure 1.2, I would take a look at using deftype instead of defstruct. If you use deftype, you can also use protocols which will make add-bst and similar functions nicer because you can use extend-type on nil, effectively allowing your code to treat nil as if it were a BST node. — Brian
– Brian, Commented Feb 8, 2011 at 1:43

mikera · Accepted Answer · 2011-02-07 17:16:19Z

3

I suspect it is because you are re-using "bst" in your function parameters, which is confusing struct-map when the value is nil....

Try renaming the function parameter to something else.

answered Feb 7, 2011 at 17:16

mikera

107k28 gold badges265 silver badges428 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

haluk Over a year ago

I renamed the parameter and now I got the following error when trying to run this (add-bst 0 (struct-map bst :left nil :right nil :key 5)). Here is the error: #<CompilerException java.lang.IllegalArgumentException: No value supplied for key: 5

mikera Over a year ago

@haluk: in your struct-map calls you need to give the key as well as the value e.g. ":key (:key bst-t)" instead of just "(:key bst-t)"

haluk Over a year ago

all right, you are right, i fixed the code according to your tip.

Collectives™ on Stack Overflow

Implementing a binary search tree in clojure

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related