Scheme Binary Search Tree Adding Elements

Question

To begin, I wanted to write a function that:

Takes in:

A list of natural numbers, (list 2 6 1 23...) that could have repeating elements called "lst"
A random binary search tree called "bst"

Outputs:

An updated binary tree that adds every number on the list to it

Code

(define (recurse-lst bst lst)
  (cond [(empty? roster) empty]
        [(empty? lst) empty]
        [else (recurse-lst (bst-add bst (first lst)) (rest lst))]))

; helper function
(define (bst-add bst sublst)
  (cond [(empty? bst) (make-node (first sublst) empty empty)]
        [(< (first sublst) (node-key bst))
         (make-node (node-key bst)
                    (bst-add (node-left bst) (first sublst))
                    (node-right bst))]
        [else
         (make-node (node-key bst) (node-left bst)
                    (bst-add (node-right bst) (first sublst)))]))

Problem

I'm currently trying to get this working for nested lists; for example (list (list 1) (list 2)...), with each sub-list only having one element in them. However, it seems that it does not work and (first sublst) in bst-add turns the sublst into a number, like (first 1).

I think I've had similar bugs in other pieces of code before, but I cannot recall when and what it was.

Thanks! Good to know. I tested my program again and it runs fine. — user14518797
great! you can post your own answer with the working code here, and later accept it, to signal that the issue is resolved. :) — Will Ness
@WillNess sorry but this happened again - I messed up on something. I was doing this for a nested list with only one element in the nested list. However, the program failed to work. I've updated the code in the question. I wanted to make a new question for this but I feel that they are too closely related. — user14518797
I've answered. for future questions please make new post(s). :) — Will Ness

Will Ness Will Ness · Accepted Answer · 2020-11-03T15:03:21

right now you have

(define (recurse-lst bst lst)
   (cond [(empty? roster)
       ....

"lst".

"roster".

you need always to include your error messages in the posts on SO.

next. you call (bst-add bst (first lst)) so the second argument in that call is already a number. yet in the definition of bst-add you name second parameter as "sublst" and treat it as a list. no need to take first again. and in fact taking first of a number is an error.

Scheme Binary Search Tree Adding Elements

1 Answers