I want to create a tree from the data provided using recursion. I am also trying to get the tree to pass an npm test, but when I run the test, it is failing. I am getting a tree, but it looks different than the one it is supposed to look like.
Here is the code (with instructions in a comment):
let data = [ { id: 'animals', parent: null }, { id: 'mammals', parent: 'animals' }, { id: 'cats', parent: 'mammals' }, { id: 'dogs', parent: 'mammals' }, { id: 'labrador', parent: 'dogs' }, { id: 'retreiver', parent: 'dogs' }, { id: 'corgi', parent: 'dogs' }, { id: 'persian', parent: 'cats' }, { id: 'siamese', parent: 'cats' }, { id: 'maineCoon', parent: 'cats' } ]; // write a function: makeTree(obj) // that takes a flat data stucture, // as seen above, and return // a tree structure as seen below. // Must use recursion. function makeTree(arr, parent) { return arr .filter((data) => data.parent === parent) .reduce( (tree, data) => [ ...tree, { ...data, child: makeTree(arr, data.id), }, ], [], ) } console.log('making tree') console.log( JSON.stringify( makeTree(data, null) , null, 2 ) ) // the tree should look like this when done let reutrn = { animals: { mammals: { dogs: { labrador: {}, retreiver: {}, corgi: {}, }, cats: { persian: {}, siamese: {}, maineCoon: {} } } } }
Advertisement
Answer
Your reduce
should produce a plain object, not an array — there is no array in your desired output. Also, your code produces a property child
, but there is no such property in your desired output. It seems like code that is specifically intended for a different output structure.
Here is the adapted reduce
call:
function makeTree(arr, parent) { return arr .filter((data) => data.parent === parent) .reduce( (tree, {id}) => ({ ...tree, [id]: makeTree(arr, id), }), {}, ); } const data = [{ id: 'animals', parent: null },{ id: 'mammals', parent: 'animals' },{ id: 'cats', parent: 'mammals' },{ id: 'dogs', parent: 'mammals' },{ id: 'labrador', parent: 'dogs' },{ id: 'retreiver', parent: 'dogs' },{ id: 'corgi', parent: 'dogs' },{ id: 'persian', parent: 'cats' },{ id: 'siamese', parent: 'cats' },{ id: 'maineCoon', parent: 'cats' }]; console.log(makeTree(data, null));
It should be noted that this is not an efficient way of doing it. It needs several passes of the whole array, giving this a quadratic time complexity, while an iterative method can do this with a linear time complexity.