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

Question

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

Recursion doesn't make much sense here. It'd be a whole lot more straightforward if it was permitted to use a different method. — CertainPerformance
– CertainPerformance, Commented Oct 2, 2022 at 4:00

trincot · Accepted Answer · 2022-10-02 07:15:22Z

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.

Scott Sauyet · Accepted Answer · 2022-10-02 14:21:19Z

Trincot gave you a way to fix the code you've been given.

But there is a simpler way to do this recursively, using the relatively new, but widely supported Object .fromEntries. With this, we get quite simple code:

const makeTree = (xs, root = null) => Object .fromEntries (
  xs .filter (({parent}) => parent == root) 
     .map (({id}) => [id, makeTree (xs, 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))

.as-console-wrapper {max-height: 100% !important; top: 0}

This has the same quadratic complexity as trincot discussed. If we wanted to we could fix that by first indexing with some sort of linear groupBy function, then doing a recursive lookup rather than a filter. I leave that as an exercise.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related