CODEWITHSUNDEEP
algorithmdata-structurestreecommon-lisp
Sim
Sim

Reputation: 4188

How to form tree into individual paths leading to each leaf

I got a tree:

(A . ((C . ((D . nil)(E . nil)))
      (B . ((F . nil)(G . nil)))))

I want to transform this tree into:

((A C D) (A C E) (A B F) (A B G))

I already implemented this function for doing so:

(defun tree->paths (tree &optional buff)
  (labels ((recurse (follow-ups extended-list)
             (if follow-ups
                 (append (list (tree->paths (car follow-ups) extended-list))
                         (recurse (cdr follow-ups) extended-list))
               nil)))
    (rstyu:aif (cdr tree)
               (recurse it (append buff (list (car tree))))
               (append buff (list (car tree))))))

But applying it results in:

(tree->paths '(A . ((C . ((D . nil) (E . nil)))
                    (B . ((F . nil) (G . nil))))))
=>
(((A C D) (A C E)) ((A B F) (A B G)))

I must be missing some kind of append/merge within the recursion but I am not seeing it.

Upvotes: 1

Views: 121

Answers (3)

user797257
user797257

Reputation:

Here, I've tried to rewrite it so that it would work linearly (because your original function would exhaust stack space). However, while doing so, I've discovered something, which you might consider in general re' your original idea:

(defun tree-to-paths (tree)
  (loop with node = tree
       with trackback = nil
       with result = nil
       with head = nil
       with head-trackback = nil
       while (or node trackback) do
       (cond
         ((null node)
          (setf node (car trackback)
                trackback (cdr trackback)
                result (cons head result)
                head (car head-trackback)
                head-trackback (cdr head-trackback)))
         ((consp (car node))
          (setf trackback (cons (cdr node) trackback)
                head-trackback (cons head head-trackback)
                head (copy-list head)
                node (car node)))
         (t (setf head (cons (car node) head)
                  node (cdr node))))
       finally (return (nreverse (mapcar #'nreverse result)))))

In your example data the result you want to receive seems intuitively correct, but you can think of it also as if there were more paths, such as for example:

A -> C -> NIL - From looking at your data, this result seems redundant, but in general, you may want to have these results too / it would be hard to filter them all out in general.

Upvotes: 0

Doug Currie
Doug Currie

Reputation: 41170

You must remove the list in (append (list (tree->paths

The tree->paths returns a list of paths; so does recurse. So, they may be appended without wrapping in a list call.

Upvotes: 1

Sim
Sim

Reputation: 4188

I started over and chose the reverse approach by going leaf to root instead of root to leaf as I tried in the question:

(defun tree->paths2 (tree)
  (labels ((recurse (follow-ups)
         (if follow-ups
         (append (tree->paths2 (car follow-ups))
             (recurse (cdr follow-ups)))
         nil)))
    (rstyu:aif (cdr tree)
           (mapcar #'(lambda(arg)
               (cons (car tree) arg))
               (recurse it))
           (list tree))))

(tree->paths2 '(A . ((C . ((D . nil) (E . nil)))
                     (B . ((F . nil) (G . nil))))))
=>
((A C D) (A C E) (A B F) (A B G))

But if there is a way to fix my first approach I'd prefer to accept such fix as an answer.

Upvotes: 0

Related Questions