Listing the paths to leaves in a tree

Question

I'm trying to write a function that finds all of the paths to the leaves in a tree. For example, given a tree that looks like this:

           1
         /  \
        2    5
       / \    \
      3   4    6

The output list would be: [[1,2,3],[1,2,4],[1,5,6]].

The type signature for this function is:branches :: Tree a -> [[a]]. Note that this uses the Tree type defined in the Data.Tree package, and that although the example tree is binary, the actual tree type is a rose tree.

Answer 1

just a simple function:

listtree :: [a] -> Tree a -> [[a]]
listtree l (Node a []) = [l++[a]]
listtree l (Node a forest) = concatMap (listtree (l++[a])) forest

use a list to record path from root to current node, and append current node's label to the path, then recursively map listtree to each subnode.

listtree [] (Node 1 [(Node 2 [(Node 3 []), (Node 4 [])]), (Node 5 [(Node 6 [])])]))

yield the desired result [[1,2,3],[1,2,4],[1,5,6]]

Answer 2

I would build the paths by adding new labels to the front of the partial path list, then reversing them for output:

listtree tree = map reverse $ traverse [] tree
  where traverse path (Node label []) = [label:path]
        traverse path (Node label xs) = concat $ map (traverse (label:path)) xs

The reason to add labels to the front of the list instead of the end is that appending takes O(N) in time and allocated memory, while adding a head takes O(1). Of course, reversing the list is also O(N), but the reversal is only done once per list...

Consequently, the above "add to head, then reverse if necessary" pattern is a pervasive idiom when working with functional algorithms and datastructures.

---

Edit: from @luqui's comment, a complementary way to get your paths is to build them from the bottom up:

listtree (Node label []) = [[label]]
listtree (Node label xs) = map (label:) $ concat $ map listtree xs

This is shorter (and possibly clearer) than my solution, and it has the additional advantage of giving you your paths in the order you want them: the paths are built starting at the leaves, instead of at the root.

Note (as with the previous solution) the path lists are extended by adding a head to the beginning of the list, rather than appending to the end.