BreadthFirstTreeRelabelling.hs

data Tree a
  = Leaf a 
  | Node (Tree a) a (Tree a)
  deriving (Eq, Show)

dfLabel :: Tree a -> Tree Int 
dfLabel = fst . go 0 where 
  go n (Leaf _)        = (Leaf n, n+1) 
  go n (Node l _ r)    =  let 
    (l', n')  = go (n+1) l
    (r', n'') = go n'   r
    in (Node l' n r', n'')
    
bfLabel :: Tree a -> Tree Int 
bfLabel t = let (result, future) = go (0:future) t in result where
  go (n:ns) (Leaf a)     = (Leaf n, n+1:ns) 
  go (n:ns) (Node l a r) = let 
    (l', ns')  = go ns  l 
    (r', ns'') = go ns' r
    in (Node l' n r', n+1 : ns'')