javascript recursion data-structures tree-structure

How to convert flat data structure to tree structure in JavaScript using recursion

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: {}
            }
        }
    }
}

Solution

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.