I have an array of objects. Each contains a "lv" property, which is an integer >= 0.
[
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
This is exported from an old software and represents a tree structure: "lv" represents how deep the node is, and its place in the tree is always relative to the previous node in the array. So the first object (A) is level 0 (root); B is level 1, and therefore a child of the previous level 0 entry (A); C is also level 1, and therefore a sibling of B (and also a child of A); and so on. The resulting structure looks like this:
├ A
│ ├ B
│ ├ C
│ │ └ D
│ │ └ E
│ └ F
└ G
I want to write a function to transform this flat array into a structure that would more closely reflect the tree structure, like this:
[
{
name: "A",
children: [
{
name: "B",
children: null
},
{
name: "C",
children: [
{
name: "D",
children: [
{
name: "E",
children: null
}
]
}
]
},
{
name: "F",
children: null
}
]
},
{
name: "G",
children: null
}
]
So basically each node has its children listed in an array under the "children" property, recursively.
I wrote the following recursive function but it breaks when it encounters a node that goes back up the tree (eg. a level 1 node coming after a level 3 node):
function buildTree(arr) {
let siblings = [], children = null
while (arr.length) {
let node = arr.shift()
if (arr.length) {
let nodeLv = +node.lv
let nextNodeLv = +arr[0].lv
if (nextNodeLv > nodeLv) {
children = buildTree(arr)
}
}
let newNode = {
name: node.name,
children: children
}
siblings.push(newNode)
}
return siblings
}
This gives me the following structure instead of the one pictured above:
└ A
├ B
└ C
└ D
└ E
└ F
└ G
So basically it works fine when building deeper, but cannot go the other way (from E to F or F to G).
What am I doing wrong here? Is there a better way to approach this?
You don't need a stack or recursion, just remember the last items of levels to put children to them:
const arr = [
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
const result = [], last = [{children: result}]; // collect last nodes of levels
for(const {lv, name} of arr){
const node = {name, children: null};
(last[lv].children ??= []).push(node);
last[lv + 1] = node;
}
console.log(result);.as-console-wrapper{max-height:100%!important};And benchmarking:
` Chrome/125
--------------------------------------------------------------------------------------
> n=7 | n=70 | n=700 | n=7000
Alexander ■ 1.00x x1m 111 | ■ 1.00x x100k 84 | ■ 1.00x x100k 858 | ■ 1.00x x10k 942
trincot 1.14x x1m 127 | 1.11x x100k 93 | 1.13x x10k 97 | 1.16x x1k 109
Andrew 6.20x x1m 688 | 5.82x x100k 489 | 5.26x x10k 451 | 5.98x x1k 563
-------------------------------------------------------------------------------------- `
const $chunk = [
{lv: 0, name: "A"},
{lv: 1, name: "B"},
{lv: 1, name: "C"},
{lv: 2, name: "D"},
{lv: 3, name: "E"},
{lv: 1, name: "F"},
{lv: 0, name: "G"},
]
const $input = [], arr = $input, data = $input;
// @benchmark Alexander
const result = [], last = [{children: result}]; // collect last nodes of levels
for(const {lv, name} of arr){
const node = {name, children: null};
(last[lv].children ??= []).push(node);
last[lv + 1] = node;
}
result;
// @benchmark trincot
function makeHierarchy(flat) {
const hierarchy = [];
const stack = [{children: hierarchy}];
for (const {lv, name} of flat) {
while (lv < stack.length - 1) stack.pop();
const obj = {name, children: null};
(stack.at(-1).children ??= []).push(obj);
stack.push(obj);
}
return hierarchy;
}
makeHierarchy(arr);
// @benchmark Andrew
{
// assign a parent to each item
data.forEach((e, i, r) => {
let last = r[i-1];
if(last) {
e.parent = last;
for(let j=(last.lv - e.lv)+1; j--;) e.parent = e.parent.parent;
}
})
// the result will directly contain the items with no parent
let result = data.filter(e => !e.parent);
// add each item to a children array created for its parent
data.filter(e => e.parent).forEach(e => (e.parent.children ??= []).push(e))
// delete unnecessary propertoes
data.forEach(e => {
delete e.parent
delete e.lv
if(!e.children?.length) e.children = null
})
result;
}
/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));