import Data.Ratio

data Tree a = Node (Tree a) a (Tree a)

cf :: Maybe Rational -> [Integer] -> Rational
cf (Just r) [] = r
cf (Just r) (x:xs) = cf (Just $ fromIntegral x + 1 / r) xs
cf Nothing  [] = 0
cf Nothing  (x:xs) = cf (Just $ fromIntegral x) xs

make :: Bool -> [Integer] -> Tree Rational
make b (x:xs) = Node (make True l) (cf Nothing $ x:xs) (make False r) where
  (l,r) = if b
    then (x+1 : xs, 2 : x-1 : xs)
    else (2 : x-1 : xs, x+1 : xs)

t :: Tree Rational
t = make False [1]

bfs :: Tree a -> [Tree a]
bfs t = t : ext (bfs t) where
  ext ((Node l _ r):qs) = l : r : ext qs
  
extract :: Tree a -> a
extract (Node _ x _) = x

main = mapM_ print $ take 200 $ map extract $ bfs t