I recently had a requirement in a project where I had to convert a flat JSON object into a nested JSON object. Instead of explaining the problem statement I will share a set of input and output arrays so that the requirement becomes clear.
const input1 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry'
},
{
pos: 2,
text: 'David'
},
{
pos: 1,
text: 'Lisa'
},
];
const output1 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry',
children: [{
pos: 2,
text: 'David'
}]
},
{
pos: 1,
text: 'Lisa'
}
];
const input2 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry'
},
{
pos: 2,
text: 'David'
},
{
pos: 2,
text: 'Edger'
},
{
pos: 1,
text: 'Lisa'
},
];
const output2 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry',
children: [{
pos: 2,
text: 'David'
},
{
pos: 2,
text: 'Edger'
}
]
},
{
pos: 1,
text: 'Lisa'
}
];
const input3 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry'
},
{
pos: 2,
text: 'David'
},
{
pos: 3,
text: 'Dexter'
},
{
pos: 2,
text: 'Edger'
},
{
pos: 1,
text: 'Lisa'
},
];
const output3 = [{
pos: 1,
text: 'Andy'
},
{
pos: 1,
text: 'Harry',
children: [{
pos: 2,
text: 'David',
children: [{
pos: 3,
text: 'David'
}]
},
{
pos: 2,
text: 'Edger'
}
]
},
{
pos: 1,
text: 'Lisa'
}
];
I am working on a solution. I am thinking if it makes sense to use recursion for this or if an alternate approach is better. I will post the solution once I solve it. But would love to have inputs from others as well :)
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;
};
I think of Array.prototype.reduce will be perfect fit for this
Matt Strom
Software Engineer, TypeScript ninja
What you're describing sounds somewhat like pre-order tree traversal but in reverse, from path to tree, where
posrepresents depth. For simplicity imagine there is a hidden root node withpos = 0at the beginning of each set of inputs.Recursion would do that job but is also overkill. Simply storing references to ancestor nodes in a stack and looping over the elements should suffice. When
posincrements by 1 (I am assuming thatposnever increments by more than 1), push the current element onto the stack. Whenposdecrements, pop the difference off of the stack. When there is no change inposappend the element into the list of children of the top element on the stack.