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
    [(&gt; (value tree) n) (merge (insert (left tree) n) (value tree)(right tree))] ; internal - go left
    [(&lt; (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)]
    [(&lt; n (cadr BST)) ; internal - go left
     (list (insert (car BST) n) (cadr BST) (caddr BST))] 
    [(&gt; n (cadr BST)) ; internal - go right
     (list (car BST) (cadr BST) (insert (caddr BST) n))] 
    [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))
    ((&lt; n (cadr BST))
     (list (insert (car BST) n) (cadr BST) (caddr BST)))
    ((&gt; 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:


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