Building a Binary Search Tree out of an unsorted list using simple recursion

Question

Given an unsorted list, say (list a b c ...) where all values are integers. Is there a way to use simple recusion to build a binary search tree.

I'm using the Beginner Student version of Racket.

I know how to solve the problem if the list is sorted, and I know how to solve the problem with an accumulator. I also know I could just sort the list and then use simple recusion. But, without any of these methods, how would I do this?

Example: Given the list (list 1 2 3 5 0 9 3 5 2) the function should produce a binary tree something like

As requested, this is my code for doing the above with an accumulator. I don't have code to perform what I've asked, because I don't know how to make code to do what I've asked.

(define-struct node (key left right))
;; A Node is a (make-node Nat BT BT)

;; A binary tree (BT) is one of:
;;  * empty
;;   * Node

;; (build-bst-from-list list) takes in an unstorted list and builds
;;    a binary search tree using an acculator

;; build-bst-from-list: (listof Num) -> BT
(define (build-bst-from-list list) 
  (build-bst-from-list/acc (rest list) (make-node (first list) empty empty)))

;; (build-bst-from-list/acc list tree) takes in an unstored list and a binary 
;;    tree and inserts all the values from the list into the tree such that
;;    the tree continues to be a binary search tree

;; build-bst-from-list/acc (listof Num) BT -> BT
(define (build-bst-from-list/acc list tree)
  (cond [(empty? list) tree]
        [else (build-bst-from-list/acc (rest list)
                                   (bst-add tree (first list)))]))
;; (bst-add tree value) takes in a binary search tree and a value and
;;    add's the value such that the tree remainder a binary search
;;    tree

;; bst-add: BT Num -> BT
(define (bst-add tree value)
  (cond [(empty? tree) (make-node value empty empty)]
        [(> (node-key tree) value) (make-node (node-key tree)
                                              (bst-add (node-left tree) value)
                                              (node-right tree))]
        [(= (node-key tree) value) tree]
        [else (make-node (node-key tree)
                         (node-left tree)
                         (bst-add (node-right tree) value))]))

Answer 1

So, it turns out all I needed to do for this was, well, simple recursion. Simply do the same as I was doing for the accumulator, but instead of inserting into the accumulator, I will insert into the recursive call which creates the rest of the list.

Something like this

(define (bst-from-list list)
  (cond [(empty? list) empty]
        [else (bst-add (bst-from-list (rest list))
                       (first list))]))


(define (bst-add tree value)
  (cond [(empty? tree) (make-node value empty empty)]
        [(> (node-key tree) value) (make-node (node-key tree)
                                              (bst-add (node-left tree) value)
                                              (node-right tree))]
        [(= (node-key tree) value) tree]
        [else (make-node (node-key tree)
                         (node-left tree)
                         (bst-add (node-right tree) value))]))