Personally I think it would be a good idea to let each node carry parent and/or root information. That way you could store tree-wide information (e.g. separator, locale, source) in the root.
Only downside I can think of is O(N) swap instead of O(1).
You mean O(N) if node carried root+parent, and O(1) if parent only, or am I missing something? I think it should only carry parent. Otherwise almost all mutating operations would invoke additional hierarchy walking, and caused updating of the root pointer everywhere. Root could be obtained from parents in O(log n), I think this is cheap enough. Anyway, I plan to get rid of separator overloads in favor of paths. I.e. if one wants a different separator, please use a path object. Thank you, Marcin