Algorithm for creating nested structure

Question

I have following structure:

{
 "list": [
 { "depth": 0, "data": "lorem1" },
 { "depth": 1, "data": "lorem2" },
 { "depth": 2, "data": "lorem3" },
 { "depth": 2, "data": "lorem4" },
 { "depth": 0, "data": "lorem5" },
 { "depth": 1, "data": "lorem6" },
 { "depth": 1, "data": "lorem7" },
 { "depth": 2, "data": "lorem8" }
 ]
}

I am looking for an algorithm on how to create from that depth a parent-child-like, nested structure.

{
 "list": [{
 "depth": 0,
 "data": "lorem1",
 "children": [{
 "depth": 1,
 "data": "lorem2",
 "children": [{
 "depth": 2,
 "data": "lorem3",
 "children": [],
 }, {
 "depth": 2,
 "data": "lorem4",
 "children": [],
 }]
 }]
 }, {
 "depth": 0,
 "data": "lorem5",
 "children": [{
 "depth": 1,
 "data": "lorem6",
 "children": [],
 }, {
 "depth": 1,
 "data": "lorem7",
 "children": [{
 "depth": 2,
 "data": "lorem8",
 "children": [],
 }]
 }]
 }
]}

The logic is like this:

• Assumption: The first item in the list always starts with depth=0
• If depth is larger than the last, it must be child of this last one

I can not get this to work. It should be recursive to have infinite nesting/depth levels.

Thank you guys for the help!

• ggorlen: Welcome to SO! Have you tried writing code? Are you stuck somewhere?
• Steven O: Hello! I am not particular stuck, I just can't find an algoritm on how to solve this.
• ggorlen: Please give it a shot and share your attempt -- otherwise, the question isn't on topic. Thanks.
• Y.T.: You could accept an answer to indicate to a wider audience that you have received a helpful answer.

Answer 1

You can use a stack to keep track of the current path in the tree. When depth increases from one to the next, then push the new node also on that stack. If not, pop items from the stack until the right depth is reached. Then you always know in which children collection you need to add the new node.

Here is an runnable implementation in JavaScript:

function algo(list) {
 // Create a dummy node to always stay at the bottom of the stack:
 let stack = [
 { "depth": -1, "data": "(root)", "children": [] }
 ];
 
 for (let node of list) {
 let newNode = { ...node, children: [] }; // Copy and add children property
 if (newNode.depth >= stack.length || newNode.depth < 0) throw "Invalid depth";
 while (newNode.depth < stack.length - 1) stack.pop();
 stack[stack.length - 1].children.push(newNode);
 stack.push(newNode);
 }
 
 return stack[0].children;
}
// Demo
let data = {
 "list": [
 { "depth": 0, "data": "lorem1" },
 { "depth": 1, "data": "lorem2" },
 { "depth": 2, "data": "lorem3" },
 { "depth": 2, "data": "lorem4" },
 { "depth": 0, "data": "lorem5" },
 { "depth": 1, "data": "lorem6" },
 { "depth": 1, "data": "lorem7" },
 { "depth": 2, "data": "lorem8" }
 ]
}
// Create a new structure, and load the transformed list in its list property:
let result = {
 "list": algo(data.list)
};
// Show result
console.log(result);

To answer to your request to do this without dummy node:

function algo(list) {
 let result = [];
 let stack = [];
 
 for (let node of list) {
 let newNode = { ...node, children: [] }; // Copy and add children property
 if (newNode.depth > stack.length || newNode.depth < 0) throw "Invalid depth";
 while (newNode.depth < stack.length) stack.pop();
 if (!stack.length) result.push(newNode);
 else stack[stack.length - 1].children.push(newNode);
 stack.push(newNode);
 }
 
 return result;
}
// Demo
let data = {
 "list": [
 { "depth": 0, "data": "lorem1" },
 { "depth": 1, "data": "lorem2" },
 { "depth": 2, "data": "lorem3" },
 { "depth": 2, "data": "lorem4" },
 { "depth": 0, "data": "lorem5" },
 { "depth": 1, "data": "lorem6" },
 { "depth": 1, "data": "lorem7" },
 { "depth": 2, "data": "lorem8" }
 ]
}
// Create a new structure, and load the transformed list in its list property:
let result = {
 "list": algo(data.list)
};
// Show result
console.log(result);

• Steven O: Hello! Thank you for your answer! This works! Is there a way to make this work without the dummy node?
• trincot: Added a version that does not create the dummy node. As you still need an array to collect the top-level nodes, I find that version less elegant.
• Steven O: You are a hero! Thank you very much for the help! I really appreciate it!