merge two trees adding only unique nodes from one tree to the next-CodePudding

I'm attempting to merge Tree2 into Tree1. The merged result contains all of existing nodes in Tree1 with the addition of the Tree2 nodes, placed at the right level in the hierarchy, that do not exist in Tree1. The final tree inputs are larger and deeper but I've struggled with the simple example trees below.

Tree1 = {"name":"A","children":[{"name":"B","children":[{"name":"C","children":[]}]},"name":"B1","children":[{"name":"C1","children":[]}]}]}
Tree2 = {"name":"A", "children":[{"name":"B", "children":[{"name":"C2", "children":[]}]}]}

merged = {"name":"A","children":[{"name":"B","children":[{"name":"C","children":[]},{"name":"C2","children":[]}]},{"name":"B1","children":[{"name":"C1","children":[]}]}]}

CodePudding user response：

You could merge by looking at the name propery of the same level.

This approach returns an array, because if you have different names for the root, the result contains at least two object.

const
    merge = (a, b) => {
        if (!Array.isArray(a)) a = [a];
        if (!Array.isArray(b)) b = [b];
        return [...a, ...b].reduce((r, o) => {
            const item = r.find(({ name }) => o.name === name);
            if (item) item.children = merge(item.children, o.children);
            else r.push(o);
            return r;
        }, []);
    },
    tree1 = { name: "A", children: [{ name: "B", children: [{ name: "C", children: [] }] }, { name: "B1", children: [{ name: "C1", children: [] }] }] },
    tree2 = { name: "A", children: [{ name: "B", children: [{ name: "C2", children: [] }] }] },
    result = merge(tree1, tree2);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response：

You can use recursion to merge your trees:

function merge(...trees){
   var m = {};
   for (var i of trees){
      m[i.name] = [...(i.name in m ? m[i.name] : []), ...i.children];
   }
   return Object.keys(m).map(function(x){return {name:x, children:m[x].length > 1 ? merge(...m[x]) : m[x]}})
}

CodePudding user response：

We note the similarity of the collected list of children and the initial parameters of our function, and can end up with a simple recursion. Here we fold the tree into an object whose keys are the names, and whose values are the collected children. Then we call Object .entries on that and map the key-value pairs into name and (through a recurive call) children properties for each. That's all it takes

const mergeTrees = (...trees) => 
  Object .entries (trees .reduce ((a, {name, children = []}) => ({
    ...a, 
    [name]: (a [name] || []) .concat (children)
  }), {})) .map (([k, v]) => ({name: k, children : mergeTrees (...v)}))

const tree1 = {name: "A", children: [{name: "B", children: [{name: "C", children: []}]}, {name: "B1", children: [{name: "C1", children: []}]}]}
const tree2 = {name: "A", children: [{name: "B", children: [{name: "C2", children: []}]}]}

console .log (mergeTrees (tree1, tree2))

.as-console-wrapper {max-height: 100% !important; top: 0}

Note that we return a forest, not a tree. If you know that all trees will have the same root, then you can extract the first element from the result.