Personal tools

99 questions/Solutions/62B

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
 
(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)