Chris Okasaki's Queue-Based Breadth-First Traversal and the Reconstruction from its Sequential Representation of Binary Tree

BFS.hs

{-# LANGUAGE DeriveGeneric #-}

{- Building a tree based on its bfs result. -}   
module BFS where

import Test.QuickCheck hiding ((><))
import GHC.Generics
import Generic.Random
import Data.Sequence (Seq (..), singleton, (><)) 

data Tree a = Leaf
              | Node { left :: Tree a
                     , label :: a
                     , right :: Tree a}
                     deriving (Show, Read, Eq, Generic)

instance Arbitrary a => Arbitrary (Tree a) where
  arbitrary = genericArbitraryRec uniform `withBaseCase` return Leaf

bfTrav :: Tree a -> Seq (Maybe a)
bfTrav t = bfTrav' $ singleton t
  where
    bfTrav' Empty     = Empty
    bfTrav' (Leaf :<| ts) = Nothing :<| bfTrav' ts
    bfTrav' (Node l x r :<| ts) = Just x :<| bfTrav' (ts :|> l :|> r)

bfBuild :: Seq (Maybe a) -> Tree a
bfBuild ds | (t :<| Empty) <- bfBuild' ds = t
  where
    bfBuild' Empty = Empty
    bfBuild' (Nothing :<| xs) = Leaf :<| bfBuild' xs
    bfBuild' (Just x :<|  xs) =
      let (ts :|> l :|> r) = bfBuild' xs
      in Node l x r :<| ts

prop t = t == bfBuild (bfTrav t)