StateT example on http://lambda.haskell.org/platform/doc/current/packages/mtl-2.1.2/doc/html/Control-Monad-State-Lazy.html, but here with Map and Traversable.

NumberTree.hs

{-# LANGUAGE  TupleSections, DeriveTraversable, DeriveFoldable, DeriveFunctor #-}

import Control.Monad.State
import Data.Traversable
import Data.Foldable 
import qualified Data.Map as M

data Tree a = Empty | Tree a (Tree a) (Tree a) 
    deriving (Show, Functor, Foldable, Traversable)

numTree :: Ord a => Tree a -> Tree Int
numTree = (`evalState` (0, M.empty)) . traverse go where        
    go a = state $ \s@(n, m) -> 
        maybe (n, (n + 1, M.insert a n m)) (,s) (M.lookup a m)

tree = Tree 0 (Tree 3 (Tree 0 Empty Empty) (Tree 2 Empty Empty)) (Tree 4 Empty Empty)

main = print $ numTree tree