CODEWITHSUNDEEP
haskelltreetree-traversal
user3654498
user3654498

Reputation: 43

How to build a list of all branches in a tree?

Have a problem with trees in Haskell. There is a tree:

data Tree a b = Leaf a | Branch (b,Tree a b) (b,Tree a b)
    deriving(Eq, Show)

tree = Branch 
         ("A",Branch 
                ("C",Leaf 3)
                ("D",Branch
                      ("G",Leaf 7)
                      ("H",Leaf 6)
                )
          )
          ("B",Branch
                 ("E",Leaf 5)
                 ("F",Leaf 4)
          )

I need to define a function, that returns a list of all branches in this tree, the Output is like this: [["A", "C"], ["A", "D", "G"],["A","D","H"],["B","E"],["B","F"]]. What I do is wrong, but have no idea how to fix it:

branch:: Tree a b -> [[b]]
branch (Leaf x) = []
branch (Branch (a,right) (b,left)) = ([y] ++ branch left) ++ ([b] ++ branch right)

The output I get is ["A","C","D","G","H","B","E","F"]

Upvotes: 3

Views: 731

Answers (1)

felix-eku
felix-eku

Reputation: 2213

I think something like this should work:

branch :: Tree a b -> [[b]]
branch (Leaf _) = [[]]
branch (Branch (a, right) (b, left)) = map (a :) (branch right) 
                                    ++ map (b :) (branch left)

Upvotes: 1

Related Questions