How Immutability is Implemented

I am trying to grasp how the trie and such in immutability is implemented, as relates to immutability in JS. I understand how there is supposed to be significant structural sharing.

My question is say you have a graph sort of structure like this:

a -- b
     |
     c
     |
     d -- h
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

So then you add an x to the system. I'll try it two different ways:

a -- b
     |
     c
     |
     d -- h -- x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

That one is just added as a leaf node.

a -- b
     |
     c
     |
     d -- h
          |
          x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

That one is added in the middle of a path.

I am wondering what the immutable data structure would be to handle these 2 situations. So essentially we have a function f : graph -> graph' that changes the graph into a "new graph", when under the hood it should only be making a small adjustment to the data structure. Not sure how this would look or how it works. My first attempt at an explanation would be something like this...

It starts of in a wrapper object which is like ImmutableJS's API layer on top of the JS objects.

 --------------------------
|                          |
|    a -- b                |
|         |                |
|         c                |
|         |                |
|         d -- h           |
|              |           |
|         e -- i -- l      |
|              |           |
|         f -- j -- m      |
|              |           |
|         g -- k -- n      |
|                          |
 --------------------------

Then you make the change and it creates a new wrapper object.

 --------------------------           --------------------------
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

Then likewise for the second example:

 --------------------------           -------------------------- 
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h           |         |                          |
|              |           |         |                          |
|              o --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

The boxes are the API objects you use, and the graphs inside are the plain JS data objects.

But in these examples the original graph structure is modified (placing a link to h in the first example, and placing an o placeholder in the second one). So I'm wondering how specifically you would make these things immutable. Every change I make to the graph I would like to "return a new object", but under the hood there is optimal structural sharing.

Thank you for your help.

from How Immutability is Implemented