CODEWITHSUNDEEP
haskelltreetraversal
JavaUser90909
JavaUser90909

Reputation: 25

How to clean up a level traversal function?

I am dealing with a general tree setup that is defined as follows:

data Tree a = Node a [Tree a] deriving (Eq, Read, Show)

With this setup, I have created a function that prints the nodes at a specific level of the tree (root is level 0, immediate children of root are level 1, etc.). This is the function:

level :: Int -> Tree a -> [a]
level 0 (Node a _) = [a]
level n (Node _ subtrees) = concatMap (level (n - 1)) subtrees

Using this function as a base, I created a second function, levelorder, which prints a list of all nodes in a tree in level order traversal. That function currently looks like this:

levelorder :: Tree a -> [a]
levelorder tree = level 0 tree ++ level 1 tree ++ level 2 tree ++ level 3 tree

While this works great for the tree I am currently working with, I would like to clean it up to where it would work with a tree of any size. As you can see, it currently only works on a tree with 4 levels (0 to 3). How would I go about achieving this to where I can still utilize the level function as a base?

Upvotes: 1

Views: 109

Answers (3)

András Kovács
András Kovács

Reputation: 30103

You can traverse the levels succesively until you run out of nodes:

levelorder :: Tree a -> [a]
levelorder t = concat $ takeWhile (not . null) $ map (`level` t) [0..]

Upvotes: 1

ScarletAmaranth
ScarletAmaranth

Reputation: 5101

You need a depth function first, so that you don't need to fix the number of levels you concatenate.

depth :: Tree a -> Int
depth (Node _ [])       = 1
depth (Node _ r@(x:xs)) = 1 + maximum (map depth r)

Then instead of fixing the number of times you use the (++) , you simply concat the results of maping the level function over each level which you draw from a list [0..depth tree].

levelorder' tree = concatMap (flip level tree) [0..depth tree]

Upvotes: 0

bheklilr
bheklilr

Reputation: 54058

If you had a function depth :: Tree a -> Int that told you how deep the tree was, it would be as simple as

levelorder tree = concatMap (\lvl -> level lvl tree) [0..depth tree]

This is not a particularly fast implementation, though, you end up traversing the tree many times.

Upvotes: 3

Related Questions