Lisp tree insertion

Question

I made a lisp code that transforms a list of numbers into a tree. The rules of the tree are that the value of the left child node should always be smaller than the value of its parent node and the value of the right child node should always be higher than the value of its parent node.

Here is my lisp code:

(defun trees (list node)
  (if (null list)
      (list node)
      (progn
        (setf valueNode (car node))
        (setf valueList (car list))
        (if (< valueNode valueList)
            (setf list (append (list (car list))
                               (cons (trees (car (cdr list)) node)
                                     (car (cdr (cdr list)))))))
        (if (> valueNode valueList)
            (setf list (append (list (car list))
                               (cons (car (cdr list))
                                     (trees (car (cdr (cdr list))) node))))))))

Normally, This command

(write (trees '(8 (7 () ()) (12 () ())) '(10 () ())))

should return

(8 (7 () ()) (12 (10 () ()) ()))

but it actually returns (8 (7 () ())).

Also, if you need more explication just tell me and i'll clarify it. (pls help me i'm very lost)

user_850781 · Answer

You are modifying list but not returning it.

Here is what you need to do:

(defun trees (list node)
  (if (null list)
      (list node)
      (let ((valueNode (car node)) (valueList (car list)))
        (if (< valueNode valueList)
            (setf list (append (list (car list))
                               (cons (trees (car (cdr list)) node)
                                     (car (cdr (cdr list)))))))
        (if (> valueNode valueList)
            (setf list (append (list (car list))
                               (cons (car (cdr list))
                                     (trees (car (cdr (cdr list))) node)))))
        list)))

now:

(trees '(8 (7 () ()) (12 () ())) '(10 () ()))
==> (8 (7 NIL NIL) 12 ((10 NIL NIL)))

PS. Please note the use of let and the correct indentation.

Lisp tree insertion

1 Answers