1
$\begingroup$

Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values should be totaled.

Example: tree1 and tree2 are merged to produce "output"

const tree1 = [
  {
    label: 'Parent A',
    value: 20,
    children: [
      {
        label: 'Child A',
        value: 100,
      }, {
        label: 'Child B',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 50,
    children: [
      {
        label: 'Child E',
        value: 200,
      },
    ],
  },
];

const tree2 = [
  {
    label: 'Parent A',
    value: 30,
    children: [
      {
        label: 'Child A',
        value: 75,
      }, {
        label: 'Child C',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 200,
    children: [
      {
        label: 'Child F',
        value: 100,
      },
    ],
  },
]

const output = [
  {
    label: 'Parent A',
    value: 50, // AMOUNTS SUMMED TOGETHER
    children: [
      {
        label: 'Child A',
        value: 175, // AMOUNTS SUMMED TOGETHER
      }, {
        label: 'Child B',
        value: 50,
      }, {
        label: 'Child C',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 250, // AMOUNTS SUMMED TOGETHER
    children: [
      {
        label: 'Child E',
        value: 200,
      },
      {
        label: 'Child F',
        value: 100,
      },
    ],
  },
];
$\endgroup$
2
  • $\begingroup$ What if there are nodes with identical names but with different parents? $\endgroup$ Mar 31 at 9:04
  • $\begingroup$ Nodes with identical names under differently named parents would not be merged. So a child node named "Child A" under "Parent A" would not be merged with a child node named "Child A" under "Parent B" $\endgroup$
    – AndyH4237
    Apr 1 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.