Difference between revisions of "99 questions/Solutions/62B"
< 99 questions | Solutions
Jump to navigation
Jump to search
(categorize) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 4: | Line 4: | ||
<haskell> |
<haskell> |
||
| − | + | atLevel :: Tree a -> Int -> [a] |
|
| + | atLevel Empty _ = [] |
||
| − | atlevel t level = loop t 1 |
||
| + | atLevel (Branch v l r) n |
||
| − | where |
||
| − | + | | n == 1 = [v] |
|
| − | + | | n > 1 = atlevel l (n-1) ++ atlevel r (n-1) |
|
| − | + | | otherwise = [] |
|
| − | | otherwise = loop l (n+1) ++ loop r (n+1) |
||
</haskell> |
</haskell> |
||
| Line 20: | 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 t n = levels t !! (n-1) |
|
</haskell> |
</haskell> |
||
| + | |||
| + | |||
| + | [[Category:Programming exercise spoilers]] |
||
Latest revision as of 13:40, 25 December 2016
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)