1
\$\begingroup\$

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] 
    )
  )
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Review! \$\endgroup\$
    – Mast
    Oct 23, 2018 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.