Find all paths from root to leaves of tree in Scheme

Question

Given a tree, I want to find the paths from the root to each leaf.

So, for this tree:

    D
   /
  B
 / \ 
A   E
 \
  C-F-G

has the following paths from root (A) to leaves (D, E, G):

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

If I represent the tree above as (A (B D E) (C (F G))) then the function g does the trick:

(define (paths tree)
  (cond ((empty? tree)
         '())
        ((pair? tree)
         (map (lambda (path)
                (if (pair? path)
                    (cons (car tree) path)
                    (cons (car tree) (list path))))
              (map2 paths (cdr tree))))
        (else
         (list tree))))

(define (map2 fn lst)
  (if (empty? lst)
      '()
      (append (fn (car lst))
              (map2 fn (cdr lst)))))

But this looks all wrong. I've not had to do this kind of thinking for a while, but I feel there should be a neater way of doing it. Any ideas for a better solution (in any language) would be appreciated.

---

EDIT - Mapping Svante's solution into Scheme gives:

(define (paths tree)
  (if (pair? tree)
      (append-map (lambda (node)
              (map (lambda (path)
                     (cons (car tree) path))
                   (paths node)))
            (cdr tree))
      (list (list tree))))

which is much neater than my original.

Answer 1

I think you could define the example tree as (root left right) each one a list. So your example tree would be: (D (B (A () (C () (F () G ) ) ) E) () ) and that is easier to traverse

Answer 2

You want a tree-search algorithm. Breadth-first or depth-first traversal would both work, and it makes no difference which, in this case, since you need to crawl the entire tree. Whenever you get to a leaf, just store the current path in your results.

Answer 3

I am more fluent in Common Lisp.

(defun paths (tree)
  (if (atom tree)
      (list (list tree))
      (mapcan (lambda (node)
                (mapcar (lambda (path)
                          (cons (car tree) path))
                        (paths node)))
              (cdr tree))))

CL-USER> (paths '(A (B D E) (C (F G))))
((A B D) (A B E) (A C F G))

Answer 4

R5RS translation of Svante's answer:

(define (accumulate op init seq)
  (define (iter ans rest)
    (if (null? rest)
        ans
        (iter (op ans (car rest))
              (cdr rest))))
  (iter init seq))

(define (flatten seq)
  (accumulate append '() seq))

(define (flatmap op seq)
  (flatten (map op seq)))

(define (atom? x)
  (not (pair? x)))

(define (paths tree)
  (if (atom? tree)
      (list (list tree))
      (flatmap (lambda (node)
                 (map (lambda (path)
                        (cons (car tree) path))
                      (paths node)))
               (cdr tree))))