Binary Search Tree in Scheme, trying to use Dr. Racket to simply return true or false if value is present in BST. Error

Question

I'm using Dr. Racket, language Pretty Big, and I'm trying to make a simple binary search tree "in?" method, that will return if a value is in the binary search tree or not. It needs to be general, accepting any kind of search tree (whether it contain strings, ints, etc.), but I'm running into this error message that is driving me nuts. Any help is appreciated, here is the code:

EDITED:: It works now, but not with anything but numbers (or at least doesn't work with strings).. New issue:

(define (bstsearch tree value)
  (cond 
  ((null? tree) #f)
  ((< value (car tree))
      (bstsearch  (cadr tree) value))
  ((> value (car tree))
      (bstsearch (caddr tree) value))
  ((= value (car tree))
      #t)
  ))

The error I'm receiving says:

<: expects type <real number> as 1st argument, given: "horse"; other arguments were: "horse"

When using:

 (bstsearch '("horse" ("cow" () ("dog" () ())) ("zebra" ("yak" ()()) ())) "horse")

as input.

Answer 1

One problem is you have your < and > reversed. Assuming you want your left sub tree to be the smaller, then (< value (car tree)) should call again with the (cadr tree).

Also you should use #t instead of (#t).

Answer 2

Regarding your new issue, < and > only work for numbers. An easy solution would be to pass the compare functions as arguments to your bstsearch procedure.

Also, as mentioned before, please indent the code correctly.

Answer 3

You shouldn't wrap the arguments in another set of parens, so use

(bstsearch  (cadr tree) value)

instead of

(bstsearch  ((cadr tree) value))

Answer 4

Your newly faced problem is because of your comparer function "=". If you change that with "equal?" function it should be generic and work in any kind of data. Comparers also should change if you want to make it generic. You must take it from user as input so generic version of it should be:

(define (bstsearch tree value comparer)

(cond 

((null? tree) #f)

  ((equal? value (car tree)) #t)

  ((comparer value (car tree))
      (bstsearch  (cadr tree) value))

  ((not (comparer value (car tree)))
      (bstsearch (caddr tree) value))

  ))

• Comparer function should be in format of (X X -> boolean), "<", ">", "string<?" are built in examples but you can write your own comparer for your own data structure too

• Note that the equal condition is on the 2. line. I hope this helps :)