data Tree a = Leaf a | Fork (Tree a) a (Tree a)
  deriving Show

numberTree :: Tree () -> Tree Integer
numberTree tree = fst $ numnum tree 1
  where
    numnum :: Tree () -> Integer -> (Tree Integer, Integer)
    numnum (Leaf ())     n = (Leaf n, n+1)
    numnum (Fork l () r) n = (Fork l' ln r', rn)
      where
        (l',ln) = numnum l n
        (r',rn) = numnum r (ln+1)

main :: IO()
main = do
  print $ numberTree (Leaf ())
  print $ numberTree (Fork (Leaf ()) () (Leaf ()))
  print $ numberTree (Fork (Leaf ()) () (Fork (Fork (Leaf ()) () (Leaf ())) () (Leaf ())))

Leaf 1
Fork (Leaf 1) 2 (Leaf 3)
Fork (Leaf 1) 2 (Fork (Fork (Leaf 3) 4 (Leaf 5)) 6 (Leaf 7))