[swannodette]

It depends on the kind of trie that you build - it's worth taking a look at Hash Array Mapped Tries http://lampwww.epfl.ch/papers/idealhashtrees.pdf

The Clojure programming language is completely designed around several immutable variants.