Dynamically generated nested tree object from array

Question

Given these two strings,

'1|100376|100377|100378' and '1|100376|100377|100379|100380'

I want to create an object that looks like this:

{
 id:"1",
 children: {
 id:"100376",
 children: {
 id:"100377",
 children: {
 id:"100378",
 children: {},
 id: "100379",
 children: {
 id:"100380",
 children: {}
 }
 }
 }
 }
}

Here is the code I have,

var tree = {};
var addTree = function(aggregateId){
 if(aggregateId){
 var arr = aggregateId.split('|'),
 remainder = aggregateId.split('|').slice(1).join('|');
 arr.reduce(function(node,id){
 return node[id] || (node[id] = {});
 }, tree);
 }
};
addTree('1|100376|100377|100378');
addTree('1|100376|100377|100379|100380');

That produces the correct nesting, but not under the keys id and children. How would I go about that?

{
 "1": {
 "100376": {
 "100377": {
 "100378": {},
 "100379": {
 "100380": {}
 }
 }
 }
 }
}

• Nayuki: How come I don't see you writing code like node.children = xx or node.id = xx?
• skilbjo: I wasn't able to figure out how to use recursion by doing something like node.children = xx or node.id = xx ... I get lost in adding the sub-level objects to the main tree object, and it also having multiple keys :(
• user663031: The two strings you give are identical, and the id 100379 in your result appears in neither.

Answer 1

var tree = {};
var addTree = function(aggregateId) {
 if (aggregateId) {
 var arr = aggregateId.split('|'),
 arr.reduce(function(node, id) {
 if (!node.id) {
 node.id = id;
 node.children = {};
 }
 return node.children;
 }, tree);
 }
};
addTree('1|100376|100377|100378');
addTree('1|100376|100377|100379|100380');
console.log(JSON.stringify(tree));
// {"id":"1","children":
// {"id":"100376","children":
// {"id":"100377","children":
// {"id":"100379","children":
// {"id":"100380","children":{}}}}}}

However, I think you might have a design flaw - children can host only one child. Are you sure you don't want it to be an array containing nodes, or even better an object that indexes nodes by key, as in your original case? It works in your original case, as you have a mapping from ids to children; but in your proposed structure, children is just one child, always.

EDIT for changed requirements: This is a bit uglier since Array.prototype.find is still not generally available. Could use .filter()[0] as hack, but that is quite inefficient. So:

var tree = [];
var addTree = function(aggregateId) {
 if (aggregateId) {
 var arr = aggregateId.split('|'),
 arr.reduce(function(children, id) {
 var node, i;
 for (i = 0; i < children.length; i++) {
 if (children[i].id == id) {
 node = children[i];
 break;
 }
 }
 if (!node) {
 children.push(node = {
 id: id,
 children: []
 });
 }
 return node.children;
 }, tree);
 }
};

• skilbjo: I see! Yes, I'd like to change it so it appends to the children object with the related IDs rather than overwrite with just the one child. I'd rather not have the mapping key be the id (would rather it be a property of the key "ID"), but would this be hard to implement?

Answer 2

You're halfway there. All you need to do is post-process your output to create the desired form, which is as simple as

function makeTree(tree) {
 if (!tree) return [];
 return Object.keys(tree) . map(function(key) {
 return { id: key, children: makeTree(tree[key]) };
 });
}

This outputs a structure which has children in an array, which you need, in case there are multiple children, as another poster pointed out. The output is:

{
 id:"1",
 children: [
 {
 id:"100376",
 children: [
 {
 id:"100377",
 children: [
 {
 id:"100378", 
 children: []
 },
 {
 id: "100379",
 children: [
 {
 id:"100380",
 children: []
 }
 ]
 }
 ]
 }
 ]
 }
 ]
}

The following code to build the intermediate representation might be somewhat more succinct that what you wrote:

function addTree(tree, input) {
 function addNodes(node, ids) {
 if (!ids.length) return; // exit recursion when done
 var id = ids.shift(); // pick off next id
 var subnode = node[id] = node[id] || { }; // find or create node
 addNodes(subnode, ids); // recursively update 
 }
 addNodes(tree, input.split('|'));
}

The way this works is that the internal function addNodes updates node with the ids in the array ids. It checks to make sure there are more ids to add, then picks off the first one, sees if the corresponding node is already there and if not creates one, then adds this id to that subnode.

Keep calling addTree on all the strings you want to process. Then, post-process tree to obtain the final output.

Using this:

> var input1 = '1|100376|100377|100378';
> var input2 = '1|100376|100379|100380';
> var tree = {};
> addTree(tree, input1) // add initial input
> tree
<"{
 "1": {
 "100376": {
 "100377": {
 "100378": {}
 }
 }
 }
 }"
> addTree(tree, input2) // add some more input
> tree
< "{
 "1": {
 "100376": {
 "100377": {
 "100378": {}
 },
 "100379": {
 "100380": {}
 }
 }
 }
 }"
> makeTree(tree)
< "[
 {
 "id": "1",
 "children": [
 {
 "id": "100376",
 "children": [
 {
 "id": "100377",
 "children": [
 {
 "id": "100378",
 "children": []
 }
 ]
 },
 {
 "id": "100379",
 "children": [
 {
 "id": "100380",
 "children": []
 }
 ]
 }
 ]
 }
 ]
 }
 ]"

Answer 3

You weren't very clear in your problem description. However, if you want an easy way to generate a tree, all you have to do is split the string at the pipe characters ("|"), then read through the array backwards.

If you want to have multiple children, you can easily adjust the logic below to make .children an array. Then, all you'd have to do is o.children.push(p) instead of o.children = p.

Since there's no way to right-reduce in JavaScript, you can just reverse the array first, before reduce-ing

var aggregate = function (s) {
 return s.split("|").reverse().reduce(function (p, c) {
 var o = {};
 o.id = c;
 o.children = p;
 return o;
 }, {});
}
console.log(aggregate("'1|100376|100377|100378'"));