Having the tree nodes inherit for MapEntry caused some serious problems when it came to the equal() and hashcode() methods.  In essence there was a confusion as to whether we were comparing the whole map or just the entry (i.e. the key value pair).
So out plan to avoid all copying when getting (key, values) from the map did not work as well as I was hoping.  Now I create a small wrapper class whenever I return a node.  It's still much better than nothing.