LISP function that returns complete binary tree

Question

I am trying to do a lisp function that will receive a list and will return a complete binary tree whose nodes are populated from the elements of the list in the same order.
For example,

(makeTree '(4 3 9 10))
(4 (3 (9 () ()) ()) (10 () ()))

To do it, I am using a function that splits the list in 2. So, what I did is tried to separate the head of the list from it's tail and then use the split function to be able to do the binary tree. But I am having trouble implementing it. Can someone help me please?
Here is my code so far:

(defun aux-head (l n)
   (if (= n 0) '()
       (cons (car l) (aux-head (cdr l)(- n 1)))))
(defun aux-tail (l n)
   (if (= n 0) l
       (aux-tail (cdr l) (- n 1))))
(defun split (lst)
   (cond
       ((null lst) '(()()))
       ((evenp (length lst))
          (list (aux-head lst (/ (length lst) 2))(aux-tail lst (/ (length lst) 2))))
       ((oddp (length lst))
          (list (aux-head lst (+ (floor (length lst) 2) 1))
                (aux-tail lst (+ (floor (length lst) 2) 1))))))
(defun make-cbtree (lst)
   (cond
       ((null lst) '(()()))
       ((car lst)
          ((split ((cdr lst)))))))

There is no error in the code so far, it’s just that I need help understanding how I have to do my code to be able to get the result I need, which is a complete binary tree of a list — Jennifer
– Jennifer, Commented Nov 10, 2020 at 22:36
I know what I have to do, it’s just that I don’t know how to do it — Jennifer
– Jennifer, Commented Nov 10, 2020 at 22:37
how can you say by the input that the result is (4 (3 (9 () ()) ()) (10 () ())), not (4 (3 (9 () ()) (10 () ())) ()) ? is there any special ruleset? because otherwise the task is ambiguous — leetwinski
– leetwinski, Commented Nov 11, 2020 at 8:42
It's not me that says it. It's what we are asked to do. I added a picture of the binary tree, maybe it can help — Jennifer
– Jennifer, Commented Nov 11, 2020 at 15:27

leetwinski · Accepted Answer · 2020-11-11 16:31:25Z

2

the common approach to creating a binary search tree is to add items one by one. It could look like this:

(defun add-node (tree val)
  (if (null tree)
      (list val () ())
      (destructuring-bind (v l r) tree
        (if (< val v)
            (list v (add-node l val) r)
            (list v l (add-node r val))))))

this one inserts the value into the proper position (rebuilding the tree, immutable style):

CL-USER> (add-node (list 1 nil nil) 2)
;; (1 NIL (2 NIL NIL))
CL-USER> (add-node (list 1 nil nil) 0)
;; (1 (0 NIL NIL) NIL)

what you need next, is to process input list one by one, adding it to the tree, starting from the empty one:

(defun make-tree (data)
  (reduce #'add-node data :initial-value nil))

CL-USER> (make-tree (list 4 3 9 10))
;; (4 (3 NIL NIL) (9 NIL (10 NIL NIL)))

you can also make up the traverse procedure:

(defun traverse (tree)
  (when tree
    (append (traverse (cadr tree))
            (list (car tree))
            (traverse (caddr tree)))))

CL-USER> (traverse (make-tree (list 4 3 9 10)))
;; (3 4 9 10)

answered Nov 11, 2020 at 16:31

leetwinski

17.9k2 gold badges21 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jennifer Over a year ago

If I use the split method that I created instead of destructuring-bind, would I get the same result?

Collectives™ on Stack Overflow

LISP function that returns complete binary tree

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related