import Data.IORef


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


numberTree :: Tree a -> IO (Tree (Int,a))
numberTree t = newIORef 0 >>= numberTreeWithRef t

numberTreeWithRef :: Tree a -> IORef Int -> IO (Tree (Int,a))
numberTreeWithRef Leaf _ = return Leaf
numberTreeWithRef (Branch l x r) ref = do
  nl <- numberTreeWithRef l ref
  n <- readIORef ref
  writeIORef ref (n+1)
  nr <- numberTreeWithRef r ref
  return (Branch nl (n,x) nr)


tree = Branch (Branch Leaf True (Branch Leaf False Leaf)) 
              True
              (Branch (Branch Leaf False Leaf) True Leaf)

test = do
  ntree <- numberTree tree
  print ntree