CODEWITHSUNDEEP
javascriptrecursiontreenodes
Patryk
Patryk

Reputation: 35

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

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.

Upvotes: 1

Views: 506

Answers (2)

trincot
trincot

Reputation: 350202

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);

Upvotes: 1

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion to merge the trees on their ids:

var 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': []}]}]};
var 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': []}]}]};
var thirdTree = {'id': '3', 'name': 'name3', 'otherProperty': 'property3', 'children': [{'id': '3a', 'name': 'name3a', 'otherProperty': 'property3a', 'children': []}, {'id': '3b', 'name': 'name3b', 'otherProperty': 'property3b', 'children': []}]};
var entryArray = [firstTree, secondTree, thirdTree];
function merge_trees(trees){
   var merger = {};
   //find matches based on id
   for (var t of trees){
      for (var i of t){
        if (!(i['id'] in merger)){
           merger[i['id']] = Object.fromEntries(Object.keys(i).map(x => [x, (new Set([i[x]]))]));
        }
        for (var k of Object.keys(i)){
           merger[i['id']][k] = new Set([...(k in merger[i['id']] ? merger[i['id']][k] : []), i[k]]);
        }
      }
   }
   var new_result = [];
   //iterate over merges
   for (var i of Object.keys(merger)){
      var result = {}
      for (var k of Object.keys(merger[i])){
         //choose whether or not to merge again based on the size of the merged children
         if (k === 'children'){
            result[k] = merger[i][k].size > 1 ? merge_trees(merger[i][k]) : [...merger[i][k]].filter(x => x.length > 1)
         }
         else{
             result[k] = merger[i][k].size === 1 ? [...merger[i][k]][0] : [...merger[i][k]] 
         }
      }
      new_result.push(result)
   }
   return new_result;
}
console.log(merge_trees(entryArray.map(x => [x])))

Upvotes: 1

Related Questions