Following are two different approaches to the solution for your question.
The naive approach is what I landed at initially, and as you can see, it is a O(n^2) solution. Matt Strom has a better approach, betterNestify — based on it — is O(n).
const naiveNestify = input => {
return input.reduceRight(
(acc, ele, idx) => {
// Make sure not to edit the objects in input
const obj = Object.assign({}, ele);
const childPos = obj.pos + 1;
const newAcc = [];
acc.forEach(e => {
if (e.pos === childPos) {
if (!obj.children) obj.children = [];
obj.children.push(e);
} else {
newAcc.push(e);
}
});
return [obj, ...newAcc];
},
[]
);
};
const betterNestify = input => {
const root = { pos: 0, children: [] };
const ancestors = [root];
for (let i = 0; i < input.length; i++) {
// Make sure not to edit the objects in input
const curr = Object.assign({}, input[i]);
const next = Object.assign({}, input[i + 1]);
const numAncestors = ancestors.length;
ancestors[numAncestors - 1].children.push(curr);
if (next) {
if (next.pos === curr.pos + 1) {
curr.children = [];
ancestors.push(curr);
} else {
const diff = curr.pos - next.pos;
ancestors.splice(numAncestors - diff, numAncestors);
}
}
}
return root.children;
};