Inorder traversal in lisp

Question

I am trying to iterate through a tree inorder in Lisp. So far, I managed building the Postorder traversal but inorder gives me headaches..

The tree's format is this:

 A
/ \
B  C          (A 2 B 0 C 2 D 0 E 0)
  / \
 D   E   

 (defun traverseTreeMain (l)
  (traverseTree l nil)
)

(defun traverseTree (l lc)
 (cond
  ((and (null l) (null lc)) nil)

  ((null l) (append nil (traverseTree lc nil)))

  ((=(cadr l) 0) (append   (list (car l))  (traverseTree (cddr l) lc)  ))

  ((= (cadr l) 1) (append nil  (traverseTree (cddr l)   
                                                        (append (   list (car l)   (- (cadr l) 1)   ) lc)
                                )   
                    )
    )

   (t (append nil (traverseTree (cddr l) (append lc (list (car l) (- (cadr     l)                                                   1))))))
)
)
;;run: (traverseTreeMain '(A 2 B 0 C 2 D 0 E 0))  --POSTORDER
;;=> (B D E C A)

Answer 1

Another solution can be found by adapting the solution to this question: Transforming trees in lisp, where it is required to transform a tree from your notation to the list notation (node left-child right-child).

Here is the solution:

(defun inorder(l)
  (if (null l)
      nil
      (inorder-sequence l)))

(defun inorder-sequence(l)
  (case (cadr l)
    (0 (values (list (car l)) (cddr l)))
    (1 (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (values (nconc left-subtree (list (car l))) rest-of-list)))
    (t (multiple-value-bind (left-subtree rest-of-list) (inorder-sequence (cddr l))
          (multiple-value-bind (right-subtree rest-of-rest) (inorder-sequence rest-of-list)
             (values (nconc left-subtree (list (car l)) right-subtree) rest-of-rest))))))

The auxiliary function inorder-sequence at each call receives the rest of the list, and returns a couple of values:

1. the list containing the inorder of the part competing to the current recursive call, and

2. a list containing the rest of the elements that must be analyzed.

In this way, at each recursive step, the function itself can use the second value to generate the relative inorder.

Note that this approach works for any kind of elements as nodes of the tree, including integers.