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?
3
Answers
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.Note that here the leaf nodes have their
children
property set to an empty array. This seems more consistent than havingnull
in that case. If you really need thenull
values, then use this variant: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.
You don’t need a stack or recursion, just remember the last items of levels to put children to them:
And benchmarking:
Open in the playground