search through a tree and return true if a node is present more than once

Question

I have a homework assignment and I need to do the following:

Function which takes a tree as its argument and returns a nil/non-nil value indicating whether the tree contains only unique nodes (ie: there are no duplicated nodes in the tree).

So far I have written the following code. I am a lisp novice and I need to finish my homework. This is the first solution that I am trying to implement. but when I compile it, it is giving me the following Error: Function position must contain a symbol or lambda expression: (FIRST TREE).

  (defun in (tree)
    (cond ((null tree)
           t)
          ((eq (first tree) (second tree))
           nil)
          ((listp (first tree))
           (or ((first tree) in  (second tree))
               ((first tree) in  (rest tree))))
          (t
           ((first tree) in (rest tree)))))

Here is my second attempt, which is also not working:

(defun flatten (structure)
  (cond ((null structure) nil)
        ((atom structure) `(,structure))
        (t (mapcan #'flatten structure))))

(defun uniNodes (inList &optional (out t) (test 0))
  (cond ((null inList)
         out)
        ((zerop test)
         (uniNodes (flatten(cons (first inList) (rest inList))) out (+ test 1)))
        ((eq t (first out))
         (uniNodes (rest inList) (compare1 (first inList) (rest inList) (first out)) test))
        ((eq nil (first out))
         out)))

(defun compare1 (a list &optional (out t))
  (cond ((null list)
         out)
        ((equal a (first list))
         nil)
        (t
         (compare1 a (rest list) (first out)))))

Can you please provide me with some insight?

Answer 1

I suggest that you recursively traverse the tree, collecting the nodes in a table.

(defun find-dupes (tree)
  (let ((table (make-hash-table)))
    (labels ((check-node (node)
               (when (consp node)
                 (when (gethash node table)
                   (return-from find-dupes node)) ; return the dupe
                 (setf (gethash node table) node) ; memorize the node
                 (check-node (car node))
                 (check-node (cdr node)))))
      (check-node tree))))

you will need to figure out how to change the above code to fit your problem.

As for your errors,

Function position must contain a symbol or lambda expression: (FIRST TREE)

means that you need to fix your function calls

(A in B)

with

(in A B)

You did not explain what is wrong with your second attempt, although it seems to be quadratic in the argument size.

Answer 2

If a tree isn't very big, then this recursive approach will do:

(defun tree-contains-duplicates-p (tree)
  (labels ((%tree-contains-duplicates-p (node table)
             (cond
               ((null node) t)
               ((consp node)
                ;; lists can't be same unless they have
                ;; same atoms, but having two `nil' lists
                ;; is a trivial case, which you want to ignore
                ;; probably
                (and (%tree-contains-duplicates-p (car node) table)
                     (%tree-contains-duplicates-p (cdr node) table)))
               (t (unless (gethash node table)
                    (setf (gethash node table) t))))))
    (not (%tree-contains-duplicates-p tree (make-hash-table)))))

Otherwise you'd like to unroll it into a loop, where you record the last action taken to traverse the tree, and upon hitting the leaf resume from there.

Looks like this should work:

(defun tree-contains-duplicates-p (tree)
  (loop with leaf = tree
     with stack = nil
     with table = (make-hash-table)
     while (or leaf stack)
     do (cond
          ((null leaf)
           (setq leaf (car stack) stack (cdr stack)))
          ((consp (car leaf))
           (when (cdr leaf)
             (setq stack (cons (cdr leaf) stack)))
           (setq leaf (car leaf)))
          (t (setq leaf (cdr leaf))))
       (when leaf
         (if (gethash (car leaf) table)
             (return t)
             (setf (gethash (car leaf) table) t)))))