Visualizing version-controlled hierarchical data

What would be the best way to visualize versioned hierarchical data in an interactive application?

Let's say we have the following hierarchical data, where the capital letters identify the enitities, and each entity has a value of type "color".

Rules are:

  1. Each node has exactly one parent.
  2. Nodes can be added and removed. But not moved!
  3. The values of nodes can be changed.

For instance, in Version2 below, D was added to B and C changed its value from green to orange:

and now, in Version3, B was deleted (thus deleting its child D) and E, F and G were added to C:

The user should be able to see any version "as it was" (what's easy), but also the overall picture of the change log (what's exactly what I'm failing to elaborate).

Adding links to "previous version" and "next version" somehow misses the point, because the user would still have the task of building this big picture in his mind, as she browses through version's snapshots.

What would be a nice way to display the change log?

p.s.: In Googling for "hierarchical versioned data, I've found about the "Tree Rings Metaphor", but it fails to support the rules 1 (single parent) and 3 (changes in node values).

Edit. I've tried to formulate the question as generic as possible, so that the knowledge shared in the replies could be more useful to others. But here is my specific scenario:

In my case, the hierarchy would be never deeper than 3 levels, and every node is expected to have dozens (but not hundreds) of siblings.

The value the nodes hold ("red", "green", "orange".. in the example) are lines of text (with around 30 characters). That is, discrete data.

One can think of the nodes as being companies, their departments and sub-departments. The value of each node is just the company/department name.

My user wants to see the historic of company's and (sub-)department's creation, extinction and name changes. (We can forget about company's merges and department swapping...)