Binary tree insert node procedure is not working as desired (Scheme)

Question

I implemented a function for inserting nodes in a binary tree.
Tree node is a list of the form (left-node key right-node).
(insert tree n) is my insert node function, where tree is a list of tree nodes in a binary search tree and I want to add the key value n as a new node.

So, (insert '(((() 4 ()) 5 (() 2 ())) 6 ()) 7) gives the output as
(((() 4 ()) 5 (() 2 ())) 6 (() 7 ())).

Now, what I want to do is something like this :
1. Define a list of values. (define (f) (list '1 `2 `3 `4 `5 ))
2. Loop through the list and enter the values one by one in a tree, starting from an empty tree.

So, when I tried to do step 2, I did the following :

(define x ()) ;; Tree x is initially empty
(insert x 2)  ;; This prints (() 2 ())
(insert x 1)  ;; This prints (() 1 ()). I want it to be ((() 1 ()) 2 ()).
(insert x 3)  ;; This prints (() 3 ()). I want it to be ((() 1 ()) 2 (() 3 ())).

That is where I am stuck.
I provide my insert function below.

(define (left tree) (list-ref tree 0))
(define (value tree) (list-ref tree 1))
(define (right tree) (list-ref tree 2))

(define (insert tree n)
  (cond
    [( null? tree ) ( list () n () )]
    [(< n (cadr tree)) (list (insert (car tree) n) (cadr tree) (caddr tree))] 
    [(> n (cadr tree)) (list (car tree) (cadr tree) (insert (caddr tree) n))] 
    [else tree] 
  )
)

Can someone suggest how I can achieve my intended outputs ?

Answer 1

Your code has three problems. Note that in the following I'm kind of rude about the code: I'm just being blunt as I'm writing quickly, and I'm not trying to be rude to you personally!

You have not defined all the abstractions you need

You want at least a function which constructs tree nodes, a function which tests for a null tree and an object which represents null trees. Here is a more complete set of abstractions:

(define null-tree '())

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (list left key right))

(define (left tree)
  (list-ref tree 0))

(define (value tree)
  (list-ref tree 1))

(define (right tree)
  (list-ref tree 2))

Your insert function does not use abstractions

It does not use the ones you have defined, let alone the missing ones, causing it to be an incomprehensible 1960s-style mess. Here is a version of it which uses abstractions throughout (this also fixes some weird spacing and dangling paren problems which are helping no-one reading your code):

(define (insert tree n)
  (cond
    [(tree-null? tree)
     (make-tree-node null-tree n null-tree)]
    [(< n (value tree))
     (make-tree-node (insert (left tree) n)
                     (value tree)
                     (right tree))]
    [(> n (value tree))
     (make-tree-node (left tree)
                     (value tree)
                     (insert (right tree) n))]
    [else tree]))

You haven't understood that insert is a function

It takes a tree and returns a tree which has the element added to it, rather than taking a tree and adding the element to it by side-effect. insert never modifies any of its arguments but rather constructs a suitable new tree (or returns the existing tree if the element being added is already there).

So in order to add a sequence of elements, for instance, you need to construct a sequence of trees with insert which have those elements added:

(define (insert-elements tree elts)
  (if (null? elts)
      tree
      (insert-elements (insert tree (first elts)) (rest elts))))

Now:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'(((() 0 ()) 1 (() 2 (() 3 (() 4 ())))) 7 (((() 20 ()) 48 ()) 202 ()))

---

Why use abstractions

If I change the abstractions for trees:

(define null-tree '/)

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (vector left key right))

(define (left tree)
  (vector-ref tree 0))

(define (value tree)
  (vector-ref tree 1))

(define (right tree)
  (vector-ref tree 2))

Then I can use exactly the same function with this new tree type:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'#(#(#(/ 0 /) 1 #(/ 2 #(/ 3 #(/ 4 /)))) 7 #(#(#(/ 20 /) 48 /) 202 /))