convert flat array to nested array

Question

I have a javascript array of objects like this:

// Id is not necessarily unique, orderly or for any specific purpose
var input = [
 { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" },
 { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" },
 { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" },
 { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" },
 { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" },
 { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" },
 { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" },
 { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" },
 { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" },
 { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" },
 { Id: 11, LongName: "North America;US;New York", Attribute1: "some attribute" },
 //...
];

How do I convert it to something like this?

var output = [
 {
 Name: "Europe",
 Children: [
 {
 Name: "Germany",
 Children: [
 {
 Name: "Frankfurt",
 Id: 1,
 Attribute1: "some attribute"
 },
 {
 Name: "Munich",
 Id: 2,
 Attribute1: "some attribute"
 }
 ]
 },
 {
 Name: "France",
 Children: [
 {
 Name: "Paris",
 Id: 12,
 Attribute1: "some attribute"
 },
 {
 Name: "Marseille",
 Id: 14,
 Attribute1: "some attribute"
 }
 ]
 }
 ],
 //...
 },
 //...
];

I did some searching and found some very similar topics: Transform array to object tree [JS] array of strings to tree data structure But what I want is a combination of nested arrays and objects, instead of a tree of objects from the above solutions.

Please help me, thanks!

• Taplar: Take the LongName and split(';') to get an array of the names. Then loop through them creating a nested structure for each key until you get to the end. And then add the element with the fields you want

Answer 1

Here is a solution using nested reduce() calls.

const output = input.reduce((a, { LongName, ...attributes }) => {
 const levels = LongName.split(';');
 
 const lastLevel = levels.pop();
 innerChildArray = levels.reduce((b, levelName) => {
 let levelIndex = b.findIndex(({ Name }) => Name === levelName);
 if (levelIndex === -1) {
 levelIndex = b.push({ Name: levelName, Children: [] }) - 1;
 }
 return b[levelIndex].Children;
 }, a);
 innerChildArray.push({ Name: lastLevel, ...attributes })
 return a;
}, []);
console.log(JSON.stringify(output, null, 2));

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

<script>
const input = [ { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" }, { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" }, { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" }, { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" }, { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" }, { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" }, { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" }, { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" }, { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" }, { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" }, { Id: 11, LongName: "North America;US;New York", Attribute1: "some attribute" },];
</script>

Answer 2

<script>
 var input = [
 { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" },
 { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" },
 { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" },
 { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" },
 { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" },
 { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" },
 { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" },
 { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" },
 { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" },
 { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" },
 { Id: 11, LongName: "North America;US;New York", Attribute1: "some attribute" }
 ];
 let output = [];
 input.forEach((item) => {
 let names = item.LongName.split(';');
 let records = output.filter((rec) => {
 return rec.Name == names[0];
 });
 let rec = { Name: names[0], Children: [] };
 if (records.length > 0) rec = records[0];
 else output.push(rec);
 let childs = rec.Children.filter((rec) => {
 return rec.Name == names[1];
 });
 let child = { Name: names[1], Children: [] };
 if (childs.length > 0) child = childs[0];
 else rec.Children.push(child);
 child.Children.push({ Name: names[2], Id: item.Id, Attribute1: item.Attribute1 });
 });
 console.log(output);
</script>

output of above program

Answer 3

Use forEach loop to traverse
On each item, split the name by ;
Check appropriate array (either parent or children array) to push. (using the ptr_arr)

const process = (input, output = []) => {
 input.forEach(({LongName, ...rest}) => {
 const keys = LongName.split(";");
 let ptr_arr = output;
 while (keys.length > 0) {
 let key = keys.shift();
 if (keys.length === 0) {
 // its leaf
 ptr_arr.push({ Name: key, ...rest });
 } else {
 let index = ptr_arr.findIndex(({ Name }) => Name === key);
 if (index === -1) {
 ptr_arr.push({ Name: key, Children: [] });
 index = ptr_arr.length - 1;
 }
 ptr_arr = ptr_arr[index].Children;
 }
 }
 });
 return output;
};
var input = [
 { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" },
 { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" },
 { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" },
 { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" },
 { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" },
 { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" },
 { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" },
 { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" },
 { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" },
 { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" },
 {
 Id: 11,
 LongName: "North America;US;New York",
 Attribute1: "some attribute",
 },
];
console.log(process(input))

Answer 4

var input = [
 { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" },
 { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" },
 { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" },
 { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" },
 { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" },
 { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" },
 { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" },
 { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" },
 { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" },
 { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" },
 { Id: 11, LongName: "North America;US;New York", Attribute1: "some attribute" },
];
output = input.reduce((result, item) => 
 { 
 let g = item.LongName.split(';'), node1, node2, node3; 
 node1 = result.find ( ({Name}) => Name === g[0] ); if (node1)
 node2 = node1.Children.find ( ({Name}) => Name === g[1] ); if (node2)
 node3 = node2.Children.find ( ({Name}) => Name === g[2] );
 if (node1 == undefined) result.push ( { Name: g[0], Children: [ { Name: g[1], Children: [ { Name: g[2], Id: item.Id, Attribute1: item.Attribute1 } ] } ] } )
 else
 if (node2 == undefined) node1.Children.push ( { Name: g[1], Children: [ { Name: g[2], Id: item.Id, Attribute1: item.Attribute1 } ] } )
 else
 if (node3 == undefined) node2.Children.push ( { Name: g[2], Id: item.Id, Attribute1: item.Attribute1 } )
 else
 console.log(item.LongName +' path already exists');
 
 return result;
 }, []
 );
 
 console.log(output);

• Miles Fan: Thanks Richard, it works. I prefer pilchard's solution because it also works for different levels of nodes, more adaptable for other scenarios.

Answer 5

This is an extended version of @pilchards answer that will handle the case of the LongName values specifying a variety of level names.

In this example the ids 412 ... 415 are a 4 level LongName nesting below an earlier added New York leaf. I also changed some of the variable names to be more indicative of their role.

// Generic way
var input = [
 { Id: 1, LongName: "Europe;Germany;Frankfurt", Attribute1: "some attribute" },
 { Id: 2, LongName: "Europe;Germany;Munich", Attribute1: "some attribute" },
 { Id: 7, LongName: "Asia;Japan;Okinawa", Attribute1: "some attribute" },
 { Id: 8, LongName: "North America;US;Seattle", Attribute1: "some attribute" },
 { Id: 10, LongName: "Asia;China;Beijing", Attribute1: "some attribute" },
 { Id: 12, LongName: "Europe;France;Paris", Attribute1: "some attribute" },
 { Id: 14, LongName: "Europe;France;Marseille", Attribute1: "some attribute" },
 { Id: 5, LongName: "Asia;Japan;Tokyo", Attribute1: "some attribute" },
 { Id: 6, LongName: "Asia;Korea;Seoul", Attribute1: "some attribute" },
 { Id: 9, LongName: "Asia;Korea;Busan", Attribute1: "some attribute" },
 { Id: 11, LongName: "North America;US;New York", Attribute1: "some attribute" },
 { Id: 412, LongName: "North America;US;New York;County1", Attribute1: "some attribute" },
 { Id: 413, LongName: "North America;US;New York;County2", Attribute1: "some attribute" },
 { Id: 414, LongName: "North America;US;New York;County3", Attribute1: "some attribute" },
 { Id: 415, LongName: "North America;US;New York;County3", Attribute1: "some attribute" },
];
output = input.reduce((rootChildren, { LongName, ...attributes }) => { 
 const levelnames = LongName.split(';');
 const leafname = levelnames.pop();
 
 // descend the tree to the array containing the leafs. insert levels as needed
 const bottomChildren = levelnames.reduce( (children, levelName) => {
 
 let levelIndex = children.findIndex ( ({Name}) => Name === levelName);
 
 if (levelIndex === -1) { // add new level at end of children
 levelIndex = children.push ({ Name: levelName, Children:[] }) - 1;
 } else
 if (!children[levelIndex].hasOwnProperty("Children")) { // add Children to existing node
 children[levelIndex].Children = [];
 }
 
 return children[levelIndex].Children; // descend
 }, rootChildren);
 
 // add the leaf
 bottomChildren.push({ Name: leafname, ...attributes });
 
 return rootChildren; 
}, []);
 
console.log(JSON.stringify(output,null,2));