Recording all paths with data in a binary tree

Question

I am trying to write a function in which records all paths that lead to data N.

can anyone give me some pointers as im getting confused, when do i record the path? as if i start at the beginning i may end up with paths that lead to know where. (Recording paths as L | R)

Can anyone give me some logic on this!

Thanks

I have worked on trees with a given path, but this i cant figure out

data Tree = N | F Tree Tree deriving Show
data Dir = L | R deriving Show
type Path = [Dir]       

so a tree could be F N (F (F N N) (F N (F N N))) and a path would be [L,L,L,R]

I have made functions to insert where there are N nodes or at a given path.

But i cant get my head round the logic of recording the paths.

Answer 1

main = print . findAllLeaves $ F N (F (F N N) (F N (F N N)))

data Tree = N | F Tree Tree deriving Show
data Dir = L | R deriving Show
type Path = [Dir]    

descend :: Tree -> Dir -> Tree
descend (F l _) L = l
descend (F _ r) R = r
descend _ _ = undefined

findAllLeaves :: Tree -> [Path]
findAllLeaves N = [[]]
findAllLeaves tree = do dir <- [L, R]
                        map (dir:) $ findAllLeaves (descend tree dir)

Result

[[L],[R,L,L],[R,L,R],[R,R,L],[R,R,R,L],[R,R,R,R]]

I use the list monad to pick both L and R "simultaneously", and descend both branches. Gotta love nondeterminism!

---

Explanation:

I hope descend is clear enough. You give it a tree and a direction, and it descends the tree in that direction.

findAllLeaves is the interesting one. How does it work?

We'll talk about the base case, findAllLeaves N = [[]], in a minute.

The recursive case is written in the list monad, with do notation. The first line is simple: choose L or R and assign this to dir. The list monad will actually choose both, and take the results for each and concatenate them together. This is they key thing to understand. It's exactly what you asked for: What are all the paths starting with L, and what are all the paths starting with R? Put those together and you have all the paths from the current node to its descendant leaf nodes.

The second line should be fairly clear from the previous paragraph's description. Descend the tree in the given direction (descend tree dir), find all leaves from that point (findAllLeaves), and then prepend the direction chosen to each of those subpaths (map (dir:)).

So why the base case [[]]? Well, think about the case just above the base case. So, for example, findAllLeaves (F N N). When we choose dir = L, we evaluate the second line:

map (L:) $ findAllLeaves (descend (F N N) L)

Descending left gives us just N

map (L:) $ findAllLeaves N

Then we've hit the base case:

map (L:) $ [[]]

Now can you see why we have that weird base case? A list with an empty list inside? Because we are going to map (L:) onto it, in other words, prepend L to each list in the outer list. This results in:

[[L]]

We get a similar result when dir = R.

[[R]]

So then the list monad concatenates those together

[[L]] ++ [[R]]

And we end up with

[[L], [R]]

If any of this is still unclear, please let me know in a comment and I'll try to clarify.

Answer 2

This isn't a complete answer, but this is the way I'd think about it: you could do a depth-first search of the tree (simple recursive calls), and just make sure you're returning the right thing on the way up. You know that when you recurse into a child subtree, you'll get a list of paths back, right? Then, you just need to think of how to get an answer given your subproblem: in this case, extend the path by the one you've traveled so far. I'd write something like

search N = [[]] -- one empty path
search (F x y) = map (L:) (search x) ++
    map (R:) (search y)

That is, prepend Left to the solutions coming from the left subproblem, and Right to the ones coming from the right subproblem.