# Binary search tree insertion in Racket

I am learning Racket and implemented a BST insert function (insert tree n) where the format for a BST node is (left-tree value right-tree).

Example

'((() 2 ()) 3 ()) is isomorphic to:

      (3)
(2)    ()
()  ()


Therefore (insert '((() 2 ()) 3 ()) 4) yields ((() 2 ()) 3 (() 4 ())):

      (3)
(2)    (4)
()  ()  () ()


Implementation

My implementation feels overly complicated. For example, I used append with cons so that the right-tree for 3, represented by (), would properly become (() 4 ()) after inserting 4.

How can I approach this problem more elegantly or more functionally?

#lang racket

(define (left tree)
(list-ref tree 0)
)
(define (value tree)
(list-ref tree 1)
)
(define (right tree)
(list-ref tree 2)
)
(define (merge left value right)
(append (cons left '()) (append (cons value '()) (cons right '())))
)
(define (insert tree n)
(cond
[(empty? tree) (append '(()) (cons n '()) '(()))] ; leaf
[(> (value tree) n) (merge (insert (left tree) n) (value tree)(right tree))] ; internal - go left
[(< (value tree) n) (merge (left tree) (value tree) (insert (right tree) n))] ; internal - go right
[(eq? (value tree) n) tree] ; internal - n already in tree
)
)


Update

Given the answer to the question, I updated my code:

(define (insert BST n)
(cond
[(empty? BST) ; leaf
(list empty n empty)]
[(< n (cadr BST)) ; internal - go left
[(> n (cadr BST)) ; internal - go right
[else
BST]
)
)


As you suspected, you don't need append for this problem. The trick is to notice that if, for example, your goal is to create the list '(1 2 3), then writing (list 1 2 3) is more straight-forward and more efficient than writing (append '(1) '(2) '(3)).

With that in mind, consider the following insertion function:

(define (insert BST n)
(cond
((null? BST)
(list empty n empty))

To run a small test, suppose you have the list '((() 3 ()) 5 (() 8 (() 10 ()))), which looks as follows:
then inserting 7 to it, ie. (insert '((() 3 ()) 5 (() 8 (() 10 ()))) 7) will produce '((() 3 ()) 5 ((() 7 ()) 8 (() 10 ()))), which looks as follows: