How to merge trees of nodes into one when elements are duplicated

Question

How could I solve a case where I have to merge trees with repeated values? For example something like that:

  const firstTree = {
    id: 1,
    name: 'name1',
    otherProperty: 'property1',
    children: [
      {
        id: '1a',
        name: 'name1a',
        otherProperty: 'property1a',
        children: []
      },
      {
        id: '1b',
        name: 'name1b',
        otherProperty: 'property1b',
        children: [
          {
            id: '1ba',
            name: 'name1ba',
            otherProperty: 'property1ba',
            children: []
          },
          {
            id: '1bb',
            name: 'name1bb',
            otherProperty: 'property1bb',
            children: []
          }
        ]
      }
    ]
  };

  const secondTree = {
    id: 1,
    name: 'name1',
    otherProperty: 'property1',
    children: [
      {
        id: '1b',
        name: 'name1b',
        otherProperty: 'property1b',
        children: [
          {
            id: '1ba',
            name: 'name1ba',
            otherProperty: 'property1ba',
            children: []
          },
          {
            id: '2ba',
            name: 'name2ba',
            otherProperty: 'property2ba',
            children: []
          }
        ]
      }
    ]
  };

const thirdTree = {
  id: '3',
  name: 'name3',
  otherProperty: 'property3',
  children: [
    {
      id: '3a',
      name: 'name3a',
      otherProperty: 'property3a',
      children: []
    },
    {
      id: '3b',
      name: 'name3b',
      otherProperty: 'property3b',
      children: []
    }
  ]
};
const entryArray = [firstTree, secondTree, thirdTree];

And I want to have as a result merged the first tree with the second and additionaly the third tree where there were no common elements :

const mergedFirstAndSecond = {
  id: 1,
  name: 'name1',
  otherProperty: 'property1',
  children: [
    {
      id: '1a',
      name: 'name1a',
      otherProperty: 'property1a',
      children: []
    },
    {
      id: '1b',
      name: 'name1b',
      otherProperty: 'property1b',
      children: [
        {
          id: '1ba',
          name: 'name1ba',
          otherProperty: 'property1ba',
          children: []
        },
        {
          id: '1bb',
          name: 'name1bb',
          otherProperty: 'property1bb',
          children: []
        },
        {
          id: '2ba',
          name: 'name2ba',
          otherProperty: 'property2ba',
          children: []
        }
      ]
    }
  ]
};
const result = [mergedFirstAndSecond, thirdTree];

I mean a solution that would also work if the duplicate elements also occurred in three different trees, not just two. I will be very grateful for any suggestions.

Answer 1

You could first create the tree as a nested map structure (where each children property is a Map instance), and merge all trees in that structure. This will allow optimised lookup to see where an entry needs to be merged into.

Once you have that, replace all these children properties back to arrays.

function mergeTrees(...trees) {
    function fillMap(src, map) {
        let dst = map.get(src.id);
        if (!dst) map.set(src.id, dst = { ...src, children: new Map });
        for (let child of (src.children ?? [])) fillMap(child, dst.children);
    }
    // Merge into nested Map structure:
    let mergedTree = new Map;
    for (let tree of trees) fillMap(tree, mergedTree);
    // Convert each map to array:
    const toArrays = map => Array.from(map.values(), node =>
        Object.assign(node, { children: toArrays(node.children) })
    );
    return toArrays(mergedTree);
}

// Demo
const firstTree = {id: 1,name: 'name1',otherProperty: 'property1',children: [{id: '1a',name: 'name1a',otherProperty: 'property1a',children: []}, {id: '1b',name: 'name1b',otherProperty: 'property1b',children: [{id: '1ba',name: 'name1ba',otherProperty: 'property1ba',children: []}, {id: '1bb',name: 'name1bb',otherProperty: 'property1bb',children: []}]}]};
const secondTree = {id: 1,name: 'name1',otherProperty: 'property1',children: [{id: '1b',name: 'name1b',otherProperty: 'property1b',children: [{id: '1ba',name: 'name1ba',otherProperty: 'property1ba',children: []}, {id: '2ba',name: 'name2ba',otherProperty: 'property2ba',children: []}]}]};
const thirdTree = {id: '3',name: 'name3',otherProperty: 'property3',children: [{id: '3a',name: 'name3a',otherProperty: 'property3a',children: []}, {id: '3b',name: 'name3b',otherProperty: 'property3b',children: []}]};

const entryArray = mergeTrees(firstTree, secondTree, thirdTree);

console.log(entryArray);