Personal tools

99 questions/Solutions/62B

From HaskellWiki

< 99 questions | Solutions
Revision as of 01:06, 14 July 2010 by Wapcaplet (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 t level = loop t 1
  where
    loop Empty _          = []
    loop (Branch a l r) n 
        | n == level = [a]
        | otherwise  = loop l (n+1) ++ loop r (n+1)

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)