Binary search tree insertion in Racket

Question

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
 (list (insert (car BST) n) (cadr BST) (caddr BST))] 
 [(> n (cadr BST)) ; internal - go right
 (list (car BST) (cadr BST) (insert (caddr BST) n))] 
 [else 
 BST] 
 )
 )

Answer 1

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))
 ((< n (cadr BST))
 (list (insert (car BST) n) (cadr BST) (caddr BST)))
 ((> n (cadr BST))
 (list (car BST) (cadr BST) (insert (caddr BST) n)))
 (else BST)))

To run a small test, suppose you have the list '((() 3 ()) 5 (() 8 (() 10 ()))), which looks as follows: enter image description here

then inserting 7 to it, ie. (insert '((() 3 ()) 5 (() 8 (() 10 ()))) 7) will produce '((() 3 ()) 5 ((() 7 ()) 8 (() 10 ()))), which looks as follows: enter image description here

• Mast: Welcome to Code Review!