We'll give you hint, but it will involve some extra work. 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. Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. You should be able to get this to work for leaf-labeled trees, too. 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) where 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