CODEWITHSUNDEEP
lispschemeracket
grifaton
grifaton

Reputation: 4046

Find all paths from root to leaves of tree in Scheme

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.

Upvotes: 3

Views: 3251

Answers (4)

Nietzche-jou
Nietzche-jou

Reputation: 14720

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))))

Upvotes: 2

Svante
Svante

Reputation: 51501

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))

Upvotes: 4

G__
G__

Reputation: 7111

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.

Upvotes: 0

Ismael
Ismael

Reputation: 344

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

Upvotes: 0

Related Questions