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?
2
Use a stack, where its current state represents a path to the current level, with node instances. Add the current node to the parent’s children list that sits at the top of the stack. Pop nodes from that stack when the level decreases.
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: []};
stack.at(-1).children.push(obj);
stack.push(obj);
}
return hierarchy;
}
// Demo with data from question
const flat = [{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 hierarchy = makeHierarchy(flat);
console.log(hierarchy);Note that here the leaf nodes have their children property set to an empty array. This seems more consistent than having null in that case. If you really need the null values, then use this variant:
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;
}
const flat = [{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 hierarchy = makeHierarchy(flat);
console.log(hierarchy);
This can be done without recursion. You can first determine the correct parent for each item, and then move each item into its correct place in the hierarchy.
const data = [{"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"}]
// 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
})
console.log(result)