# 99 questions/Solutions/62B

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

(One intermediate revision by one user not shown) | |||

Line 4: | Line 4: | ||

<haskell> |
<haskell> |
||

− | atlevel :: Tree a -> Int -> [a] |
+ | atLevel :: Tree a -> Int -> [a] |

− | atlevel t level = loop t 1 |
+ | atLevel Empty _ = [] |

− | where |
+ | atLevel (Branch v l r) n |

− | loop Empty _ = [] |
+ | | n == 1 = [v] |

− | loop (Branch a l r) n |
+ | | n > 1 = atlevel l (n-1) ++ atlevel r (n-1) |

− | | n == level = [a] |
+ | | otherwise = [] |

− | | otherwise = loop l (n+1) ++ loop r (n+1) |
||

</haskell> |
</haskell> |
||

Line 19: | Line 19: | ||

levels (Branch a l r) = [a] : zipWith (++) (levels l) (levels r) |
levels (Branch a l r) = [a] : zipWith (++) (levels l) (levels r) |
||

− | atlevel :: Tree a -> Int -> [a] |
+ | atLevel :: Tree a -> Int -> [a] |

− | atlevel t n = levels t !! (n-1) |
+ | atLevel t n = levels t !! (n-1) |

</haskell> |
</haskell> |

## Latest revision as of 08:49, 2 December 2010

Collect the nodes at a given level in a list

A node of a binary tree is at level N if the path from the root to the node has length N-1. The root node is at level 1. Write a predicate atlevel/3 to collect all nodes at a given level in a list.

atLevel :: Tree a -> Int -> [a] atLevel Empty _ = [] atLevel (Branch v l r) n | n == 1 = [v] | n > 1 = atlevel l (n-1) ++ atlevel r (n-1) | otherwise = []

Another possibility is to decompose the problem:

levels :: Tree a -> [[a]] levels Empty = repeat [] levels (Branch a l r) = [a] : zipWith (++) (levels l) (levels r) atLevel :: Tree a -> Int -> [a] atLevel t n = levels t !! (n-1)