CODEWITHSUNDEEP
treelispcommon-lisp
Mocktheduck
Mocktheduck

Reputation: 1423

Path from root to a given node n-ary tree lisp without map/lambda/labels

I know this has been asked before but it has been solved only with map/lambda/labels and I want it solved as basic as possible

I want to return the path from the root to a given node of a tree that looks like this:

  A
 / \
B   C
   / \
  D   E

given as: (A 2 B 0 C 2 D 0 E 0) Path from A (root) to given node E is: A C E

I have no idea how to keep the path before finding where exactly the element is. Should I save the partial result? Any help please?

I tried checking if the element is in but... I just can't construct the path

(defun isinh (l a p)
  (cond ((null l) p)
        ((equal (car l) a) (isinh (cdr l) a 1))
        (t (isinh (cdr l) a p))))

(defun isin (l a)
  (cond (t (isinh l a 0))))

(defun p15 (l el)
  (cond ((null l) '())
        ((equal (car l) el) (list el))
        ((and (listp (car l))
              (= (isin (car l) el)))
         (p15 (car l) el))
        ((and (listp (cadr l))
              (= (isin (cadr l) el)))
         (p15 (cadr l) el))
        ((not (equal (car l) el))
         (cons (car l) (p15 (cdr l) el)))))

Upvotes: 0

Views: 746

Answers (1)

Renzo
Renzo

Reputation: 27414

A possible solution is to transform the tree in a list structure, where the first element is the root, the second element is the left child, and third element is the right child, and then search a path with a simple recursive function.

To transform the tree in a list structure, see the answers to this question: transforming trees in lisp.

A recursive function that finds the path is the following:

(defun path(tree el)
  (cond ((null tree) nil)
        ((eql (first tree) el) (list el))
        (t (let ((lpath (path (second tree) el)))
             (if lpath
               (cons (first tree) lpath)
               (let ((rpath (path (third tree) el)))
                 (when rpath
                   (cons (first tree) rpath))))))))

UPDATE

The previous version works only for binary trees, a versione for n-ary trees is the following:

(defun path(tree el)
  (cond ((null tree) nil)
        ((eql (car tree) el) (list el))
        (t (loop for child in (rest tree)
              for child-path = (path child el)
              when child-path
              do (return-from path (cons (car tree) child-path))))))

(path '(a (b (c)) (d (e) (f)) (g (h) (i (j)))) 'j)  ;  =>  (A G I J)

Upvotes: 1

Related Questions