list not accepting special character at end

Question

I am trying examples from this page While I am trying to create a post-order traversal seeing example of pre-order traversal,

(defun bin-tree-postorder (B)
  "Create a list containing keys of B in preorder."
  (if (bin-tree-leaf-p B)
      (list (bin-tree-leaf-element B))
    (let ((elmt  (bin-tree-node-element B))
          (left  (bin-tree-node-left    B))
          (right (bin-tree-node-right   B)))
      (cons (bin-tree-postorder left)
            (cons (bin-tree-postorder right) elmt)))))

I am getting (((2) (3) . +) ((7) (8) . -) . *) But I desire '(2 3 + 7 8 - *). When I try to use append it says " APPEND: A proper list must not end with" error. In case of prepend its fine to append any +, -, / etc but at the end why is it complaining ?

I need help on fixing this.

Answer 1

You're not constructing what you what to in this code:

(cons (bin-tree-postorder left)
      (cons (bin-tree-postorder right)
            elmt))

Consider the following:

> (cons 2 (cons 3 '+))
(2 3 . +)

> (cons (list 2) (cons (list 3) '+))
((2) (3) . +)

Have a look at this answer to Dot notation in scheme for more about what the . notation in a list means, but the condensed version is that a proper list in Lisps (including Scheme) is either:

• the empty list (); or
• a cons cell whose car is the first element of the list and whose cdr is a proper list that is the rest of the list.

That means that to make a list (2 3 +), you would need the equivalent of

(cons 2 (cons 3 (cons '+ '())))

What you've actually got is different:

You're not constructing what you what to in this code:

(cons (bin-tree-postorder left)
      (cons (bin-tree-postorder right)
            elmt))

• Since left is 2, (bin-tree-postorder left) is (2)
• Since right is 3, (bin-tree-postorder right) is (3)
• Since elmt is +, elmt is (3)

Then what you've got is

> (cons '(2) (cons '(3) '+))
((2) (3) . '+)

If you want to use append, then you'll need to make the last argument a proper list. E.g.:

(append (bin-tree-postorder left) (bin-tree-postorder right) (list elmt))