haskell binary tree path function

Question

I am trying to define a function which will return the list of all paths through a given binary tree. I have the following functions defined already:

data BTree a = Leaf a | Node a (BTree a) (BTree a)
     deriving (Show,Eq)

paths :: BTree a -> [[a]] 
paths (Leaf a) = [[]]
paths (Node x left right) = map (x:) (paths left ++ paths right)

With this function I have the following results for example: [[5,4],[5,4],[5,3],[5,3]] . But I was supposed to have as a result the output [[5,4,1],[5,4,2],[5,3,3],[5,3,4]]. Do anyone know why i dont get the 3rd value? Thank you

duplode · Accepted Answer · 2018-02-18 15:16:02Z

2

Your BTree type is:

data BTree a = Leaf a | Node a (BTree a) (BTree a)

Note that, unlike a list, it is never empty: both the leaves and the nodes contain values of type a. That being so, if you have a case in paths that always produces empty lists, such as...

paths (Leaf a) = [[]]

... you are necessarily throwing values away. What you want instead is:

paths :: BTree a -> [[a]] 
paths (Leaf a) = [[a]]
paths (Node x left right) = map (x:) (paths left ++ paths right)

answered Feb 18, 2018 at 15:16

duplode

34.5k7 gold badges88 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

haskell binary tree path function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related