Locally editing a purely functional tree

Let's define a tree T:

    A
   / \
  B   C
 / \
D   E

Let's say a new node is added to E, yielding T':

    A
   / \
  B   C
 / \
D   E
     \
      G

In a mutable language this is an easy task - just update E's children and we're done. However, in an immutable world it is necessary to first know the path to E, then derive E' from E + new child, then derive B' and then finally A' ( = T').

This is cumbersome; ideally, there would be some function that would take the values of E and G (and possibly T) and produce T', without supplying the path to E.

I see two possible ways to attack this problem:

• parent references - this way, every node would be able to derive its path to the root. Two problems: creating two mutually referencing nodes (i.e. parent <-> child) is a problem in a purely functional language (any easy solutions?); and whenever E -> E' is derived, all of E''s children need to be newly derived as well, since they now store the old value of E instead of E'.
• zippers - every node stores a zipper on creation, derived from its parent zipper. The mutually referencing problem disappears, but still, when E -> E' is derived, all of E''s childrens' zippers need to be derived as well, since they now point to the old tree E.

Is what I desire even possible with a reasonable performance in mind? Many thanks for any input!