Algorithm (JS or Pseudocode) to get difference between two XML trees

I've created a simple solution based on your description of the problem. It may not be truly optimal, but it gets the job done (hopefully). See if this is what you need.

We'll use the xml-parse package to process XML.

TL;DR: Get the full code here.

So, to solve this problem, we will go through two steps.

STEP 1: Create maps of the XML files

Let's define a data structure called "map" (should've chosen a more descriptive name but couldn't think of one). This map will be a dictionary.

Our map consists of key-value pairs.

• The key is a path. Our map will contain all existing paths in the XML structure.
• The value is another dictionary:
  • The key is the name of the element.
  • The value is the tag of the element.

So the maps of the two example XML structures you provided will be like this:

Old map:

{
   "/rootDir":{
      "childDir":"dir",
      "linux.txt":"file",
      "img.png":"file"
   },
   "/rootDir/childDir":{
      "hello.jpg":"file"
   }
}

New map:

{
   "/rootDir":{
      "childDir":"dir",
      "photos":"dir",
      "img.png":"file"
   },
   "/rootDir/childDir":{
      "hello.jpg":"file",
      "interesting.brain":"file"
   },
   "/rootDir/photos":{
      "me.dng":"file"
   }
}

The recursive function to build a map from an XML structure will be like this:

// recursive function to build map
function buildMap(element, path, map) {
  map[path] = {}
  // const childElements = element.childNodes.filter(childNode => childNode.type === 'element');
  for (const childNode of element.childNodes) {
    // skip text (because the xml-parse package also returns the unnecessary texts in an XML structure, e.g. line breaks)
    if (childNode.type === 'text') continue;

    // process child element
    // add child element's name to indicate that this path has a child with this name
    // use child element's type (dir/file) as the value
    map[path][childNode.attributes.name] = childNode.tagName;

    // if child element is dir, process it recursively
    if (childNode.tagName === 'dir') buildMap(childNode, `${path}/${childNode.attributes.name}`, map);
  }
}

STEP 2: Get the differences between the two maps

Now we'll derive the changes from the maps.

Basically, what we'll do is traverse through the paths of the old map, get the set of children in each path (from both maps) and compare the two sets of children to get the changes we need.

The functions for this step are as follows:

// function to get the differences between two maps
function diffMaps(oldMap, newMap) {
  const changes = [];
  // traverse each path of the old map
  for (const key of Object.keys(oldMap)) {
    // get children in this path for both old map and new map
    const oldChildren = oldMap[key];
    const newChildren = newMap[key];
    changes.push(...diffChildren(key, oldChildren, newChildren));
  }
  return changes;
}

// function to get the differences between the children of two maps
function diffChildren(path, oldChildren, newChildren) {
  const changes = [];
  // traverse each child of the old children
  for (const key of Object.keys(oldChildren)) {
    // if new children also have that child ==> no change ==> remove that child from new children and continue
    if (newChildren[key]) {
      // the reason for deleting is that after we have deleted all the keys that are present in old children, the remaining keys in new children will be the newly added ones.
      delete newChildren[key];
      continue;
    }

    // new children don't have that child ==> deleted ==> add to changes
    const type = oldChildren[key];
    changes.push({
      node: type === 'dir' ? `<dir name="${key}">` : `<file name="${key}"/>`,
      path: path,
      change: 'deleted'
    });
  }

  // traverse each child of the new children and add them to changes
  for (const key of Object.keys(newChildren)) {
    const type = newChildren[key];
    changes.push({
      node: type === 'dir' ? `<dir name="${key}">` : `<file name="${key}"/>`,
      path: path,
      change: 'added'
    });
  }

  return changes;
}

FINALLY: Testing

Now that we have the necessary functions, just plug in our data and run :)

const oldXmlString = String.raw`
<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
    </dir>
    <file name="linux.txt"/>
    <file name="img.png"/>
</dir>
`.trim();

const newXmlString = String.raw`
<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
        <file name="interesting.brain"/>
    </dir>
    <dir name="photos">
        <file name="me.dng"/>
    </dir>
    <file name="img.png"/>
</dir>
`.trim();

const oldXml = xml.parse(oldXmlString);
const newXml = xml.parse(newXmlString);

const oldRoot = oldXml[0];
const newRoot = newXml[0];

// maps with path as key and child nodes' names as value
const oldMap = {};
const newMap = {};

buildMap(oldRoot, `/${oldRoot.attributes.name}`, oldMap);
buildMap(newRoot, `/${newRoot.attributes.name}`, newMap);

const diffs = diffMaps(oldMap, newMap);
console.log(diffs);

Output:

[ { node: '<file name="linux.txt"/>',
    path: '/rootDir',
    change: 'deleted' },
  { node: '<dir name="photos">',
    path: '/rootDir',
    change: 'added' },
  { node: '<file name="interesting.brain"/>',
    path: '/rootDir/childDir',
    change: 'added' } ]