Find all paths from root to leaves of tree in Scheme
- by grifaton
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 (g tree)
(cond ((empty? tree)
'())
((pair? tree)
(map (lambda (path)
(if (pair? path)
(cons (car tree) path)
(cons (car tree) (list path))))
(map2 g (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.
