We'll give you a hint, but it will require some extra thought.

The hint is a solution to this exercise taken from the source code that accompanies the Glasgow Haskell Compiler (underneath /Control/Monad/State/Strict.hs).

We're not going to massage it in any way. If you want to make use of it, you'll have to figure out for yourself what's going on. This should be within your reach at this point. See our page on translating between OCaml Scheme and Haskell for guidance. See our state monad tutorial for explanation of get and put.

Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. It shouldn't be too hard to get a similar strategy to work for leaf-labeled trees.

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
type Table a = [a]

numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
numberTree Nil = return Nil
numberTree (Node x t1 t2)
       =  do num <- numberNode x
             nt1 <- numberTree t1
             nt2 <- numberTree t2
             return (Node num nt1 nt2)
    numberNode :: Eq a => a -> State (Table a) Int
    numberNode x
       = do table <- get
            (newTable, newPos) <- return (nNode x table)
            put newTable
            return newPos
    nNode::  (Eq a) => a -> Table a -> (Table a, Int)
    nNode x table
       = case (findIndexInList (== x) table) of
         Nothing -> (table ++ [x], length table)
         Just i  -> (table, i)
    findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
    findIndexInList = findIndexInListHelp 0
    findIndexInListHelp _ _ [] = Nothing
    findIndexInListHelp count f (h:t)
       = if (f h)
         then Just count
         else findIndexInListHelp (count+1) f t


-- numTree applies numberTree with an initial state:

numTree :: (Eq a) => Tree a -> Tree Int
numTree t = evalState (numberTree t) []

testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
numTree testTree

~~> Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil