CODEWITHSUNDEEP
haskelltreedepth-first-search
neural.atlant
neural.atlant

Reputation: 225

Haskell: depth-first search for ordered tree

First of all, I have a data type for ordered trees:

data OrdTree a = OrdTree a [OrdTree a]
                    deriving (Show)

I need to get a list of all nodes in order of DFS (depth-first search).

Here is my attempt to solve this:

dfsTreeList :: OrdTree a ->  [a]                       
dfsTreeList (OrdTree a (x:xt)) = a : (dfsTreeList x) ++ (dfsTreeList (OrdTree a xt))                          
dfsTreeList (OrdTree a []) = a : []

But a new problem appears: every non-last node is included in the list twice.

For instance, input data:

dfsTreeList (OrdTree 7 [(OrdTree 3 [(OrdTree 1 []), (OrdTree 4 [])]), (OrdTree 10 [(OrdTree 8 []), (OrdTree 12 [])])])

And result:

[7,3,1,3,4,3,7,10,8,10,12,10,7]

Does someone have any ideas? Thanks for any reply.

Upvotes: 1

Views: 1041

Answers (1)

chi
chi

Reputation: 116139

Here

dfsTreeList (OrdTree a (x:xt)) = a : (dfsTreeList x) ++ (dfsTreeList (OrdTree a xt))

you are duplicating the a. You could try applying the function to every subtree in the list, e.g.

dfsTreeList (OrdTree a xs) = a : concat (map dfsTreeList xs)

You can also use concatMap or >>= to the same effect.

Upvotes: 3

Related Questions