This question builds on many similar ones like Construct hierarchy tree from flat list with parent field?
However the twist is that there is no parent id. e.g.
[
{id: 1, depth: 1, ...},
{id: 2, depth: 2, ...},
{id: 3, depth: 3, ...},
{id: 4, depth: 2, ...},
{id: 5, depth: 1, ...},
{id: 6, depth: 2, ...},
{id: 7, depth: 2, ...},
{id: 8, depth: 1, ...},
{id: 9, depth: 2, ...},
{id: 10, depth: 3, ...},
{id: 11, depth: 3, ...},
]
What is a performant way to construct the following tree?
Note that the children always come after the parent i.e. one can see the tree from the depth value. For example, id 2 is a child of id 1 since its depth is 2 and id 1 has a depth of 1. id 3 is a child of id 2 since id 3 has a depth of 3. id 4 is a child of id 1 not id 3 because id 4 has a depth of 2 (a step up) from id 3's depth of 3
\\tree digram
1
2
3
4
5
6
7
8
9
10
11
Should have values like
[
{id:1, depth:1, children: [
{id: 2, depth: 2, children: [...]},
...
]},
{id:5, depth:1, children: [...]},
{id:6, depth:1, children: [...]},
]
You can use an array for this that has an index for each depth. At every moment, it will represent a path from the (virtual) root to the current node. When dealing with a node, its parent will sit at index depth-1, where it can be inserted in that parent's children property, and the node itself will be placed at index depth:
function createForest(flatdata) {
const path = [{ children: [] }];
for (const obj of flatdata) {
path[obj.depth - 1].children.push(path[obj.depth] = { ...obj, children: [] });
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 1},{id: 2, depth: 2},{id: 3, depth: 3},{id: 4, depth: 2},{id: 5, depth: 1},{id: 6, depth: 2},{id: 7, depth: 2},{id: 8, depth: 1},{id: 9, depth: 2},{id: 10, depth: 3},{id: 11, depth: 3}];
const roots = createForest(flatdata);
console.log(roots);If the depth values do not correspond to the actual depth of the nodes, but leave gaps, then use a "dictionary" (a plain object) to record the mapping of the depth property values with which real depth they correspond with:
function createForest(flatdata) {
const path = [{ children: [] }];
const depthMap = { 0: 0 };
for (const obj of flatdata) {
path[(depthMap[obj.depth] ??= path.length) - 1].children.push(
path[depthMap[obj.depth]] = { ...obj, children: []}
);
}
return path[0].children;
}
// demo
const flatdata = [{id: 1, depth: 10},{id: 2, depth: 20},{id: 3, depth: 30},{id: 4, depth: 20},{id: 5, depth: 10},{id: 6, depth: 20},{id: 7, depth: 20},{id: 8, depth: 10},{id: 9, depth: 20},{id: 10, depth: 30},{id: 11, depth: 30}];
const roots = createForest(flatdata);
console.log(roots);If however, the only irregularity is that the depth does not always start at 1, but sometimes at 2, it will be more efficient to prefix the input data with a dummy depth-one node, use the first function, and then remove the dummy "root" (with depth 1) from the result.
Go through the array and add each item to the tree as well as to a trail of breadcrumbs. Each next item either goes as a child to the last one or you backtrack through the breadcrumb trail to the correct depth where it needs to be inserted:
const peek = arr =>
arr[arr.length-1];
function toTree(arr) {
const tree = [];
const trail = [];
for (const item of arr) {
while ((peek(trail)?.depth ?? 0) >= item.depth) {
trail.pop();
}
const current = peek(trail)?.children ?? tree;
const treeNode = {...item, children: []};
current.push(treeNode);
trail.push(treeNode);
}
return tree;
}
const array = [
{id: 1, depth: 1, },
{id: 2, depth: 2, },
{id: 3, depth: 3, },
{id: 4, depth: 2, },
{id: 5, depth: 1, },
{id: 6, depth: 2, },
{id: 7, depth: 2, },
{id: 8, depth: 1, },
{id: 9, depth: 2, },
{id: 10, depth: 3 },
{id: 11, depth: 3 },
]
console.log(toTree(array));This solution clones each item, in order to add the .children property. If no cloning is necessary, item can be directly mutated.
You could take an array of the last inserted objects.
const
data = [{ id: 1, depth: 1 }, { id: 2, depth: 2 }, { id: 3, depth: 3 }, { id: 4, depth: 2 }, { id: 5, depth: 1 }, { id: 6, depth: 2 }, { id: 7, depth: 2 }, { id: 8, depth: 1 }, { id: 9, depth: 2 }, { id: 10, depth: 3 }, { id: 11, depth: 3 }],
result = data.reduce((r, { depth, ...o }) => {
r[depth - 1].push({ ...o, children: r[depth] = [] });
return r;
}, [[]])[0];
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }