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

A possible approach here is first to construct the tree out of the preorder notation. To represent the binary tree nodes, we can use three-element lists (triplets). The first item in the triplet is the symbol: A, B, ... the next two elements are the left and right references.

Now, how to turn the syntax:

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

into a tree? One approach is to reverse the syntax first:

(reverse '(A 2 B 0 C 2 D 0 E 0)) -> (0 E 0 D 2 C 0 B 2 A)

And now, we treat this as a little computer program written in a simple stack-based language with two instructions: numbers and symbols. We scan the syntax from left to right. When we see a number, we push it on the stack. When we see a symbol, we pop the top of a stack, which should be a number. That number then tells us how many nodes to pop off the stack: 0, 1 or 2. We do as we are told, and construct a tree out of the symbol, and that many child nodes. Then we put the tree on the stack. Code:

(defun build-tree (syntax)
  (let ((rs (reverse syntax))
        (stack))
    (dolist (item rs (pop stack))  ;; heart of the interpreter loop
      (cond ((integerp item) (push item stack))  ;; integer instruction
            ((symbolp item) (let ((num (pop stack)))  ;; sym instruction
                              ;; construct node using backquote, and
                              ;; put it on the stack.
                              (push `(,item ,@(loop repeat num
                                                    collect (pop stack)))
                                    stack)))))))

Note that the (pop stack) expression in the dolist calculates the result value for dolist, which is the return value for the function. When we are done interpreting the syntax, the complete tree is the only item left in the stack, and so we pop that.

No effort is put into handling any errors in the syntax; we assume that the syntax is an error-free description of a tree.

Note: cond in the interpreter can be replaced by typecase or etypecase.

Test:

(build-tree '(A 2 B 0 C 2 D 0 E 0)) -> (A (B) (C (D) (E)))

Additional cases:

(build-tree nil) -> NIL

(build-tree '(B 0)) -> (B)

Looks good. The tree is rooted at A, with two children (B) and (C (D) (E)). (B) means a B node with no children, and so Forth ... pardon the pun!

This resulting structure can be walked in any order with ease.

Here is preorder traversal, using a callback function to process the symbols in the nodes. To "visit" means to pass the symbol to the callback. The user of the function specifies a function which does something, like collect the symbols passed to the callback:

(defun preorder (tree callback-fn)
  (when (consp tree)
    (preorder (second tree) callback-fn) ;; process children first
    (preorder (third tree) callback-fn)
    (funcall callback-fn (first tree)))) ;; then visit parent

Test:

(let ((output))
   (preorder (build-tree '(A 2 B 0 C 2 D 0 E 0))
             (lambda (item) (push item output)))
   (nreverse output))

--> (B D E C A) ;; correct

The callback lambda pushes the items it receives into the output list, which is then destructively reversed.

Inorder is left as a trivial exercise for the reader.

Answer 2

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.