Haskell- lists from root to leaves

Question

The code suppose to return a list of every path from a root to a leaf in the tree, in order from left to right. Nodes with one child (one Tip and one Bin) are not considered leaf nodes.

I tried to code like

paths :: Tree a -> [[a]]
paths Tip = [[]]
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)

But it seems return the path include nodes with one child. This will lead to paths like [[4,3],[4]] on Bin (Bin Tip 3 Tip) 4 Tip.

Answer 1

This is due to the fact that your paths Tip = [[]] returns a list with one element: an empty list.

This thus means that for a Bin Tip 4 (Bin Tip 3 Tip) for example, the paths left will thus return a [[]], and you prepend that list with 4, so [4] will be yielded as well.

If you change this to paths Tip = [], you fix the problem, since then it will not yield an element:

paths :: Tree a -> [[a]]
paths Tip = []
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)