Building a tree recursively in JavaScript

Question

I am trying to build a tree recursively from an array of objects. I am currently using the reduce() method to iterate through the items in the array and figure out which children belong to a particular item and populating it, then recursively populating the children of those children and so on. However, I have been unable to take the last nodes(e.g persian and siamese in this case) and put them in array(see expected and current output below)

    let categories = [
        { id: 'animals', parent: null },
        { id: 'mammals', parent: 'animals' },
        { id: 'cats', parent: 'mammals' },
        { id: 'dogs', parent: 'mammals' },
        { id: 'chihuahua', parent: 'dogs' },
        { id: 'labrador', parent: 'dogs' },
        { id: 'persian', parent: 'cats' },
        { id: 'siamese', parent: 'cats' }
    ];

   const reduceTree = (categories, parent = null) => 
    categories.reduce(
        (tree, currentItem) => {

            if(currentItem.parent == parent){
               tree[currentItem.id] = reduceTree(categories, currentItem.id);  
            }              

            return tree;
        },
        {}        
   )  

   console.log(JSON.stringify(reduceTree(categories), null, 1));

expected output:

{
    "animals": {
        "mammals": {
            "cats": [     // <-- an array of cat strings
                "persian",
                "siamese"
            ],
            "dogs": [     // <-- an array of dog strings
                "chihuahua",
                "labrador"
            ]
        }
    }
}

current output:

{
    "animals": {
        "mammals": {
            "cats": {       // <-- an object with cat keys
                "persian": {},
                "siamese": {}
            },
            "dogs": {       // <-- an object with dog keys
                "chihuahua": {},
                "labrador": {}
            }
          }
     }
}

How should I go about solving the problem?

Answer 1

I put a condition to merge the result as an array if a node has no child. Try this

let categories = [
        { id: 'animals', parent: null },
        { id: 'mammals', parent: 'animals' },
        { id: 'cats', parent: 'mammals' },
        { id: 'dogs', parent: 'mammals' },
        { id: 'chihuahua', parent: 'dogs' },
        { id: 'labrador', parent: 'dogs' },
        { id: 'persian', parent: 'cats' },
        { id: 'siamese', parent: 'cats' }
    ];

   const reduceTree = (categories, parent = null) => 
    categories.reduce(
        (tree, currentItem) => {

            if(currentItem.parent == parent){
                let val = reduceTree(categories, currentItem.id);
                if( Object.keys(val).length == 0){
                    Object.keys(tree).length == 0 ? tree = [currentItem.id] : tree.push(currentItem.id);
                }
                else{
                    tree[currentItem.id] = val;
                }
            } 
            return tree;
        },
        {}
   )  

   console.log(JSON.stringify(reduceTree(categories), null, 1));

NOTE: if your data structure changes again this parser might fail for some other scenarios.

Answer 2

Here is a solution without recursion:

const categories = [{ id: 'animals', parent: null },{ id: 'mammals', parent: 'animals' },{ id: 'cats', parent: 'mammals' },{ id: 'dogs', parent: 'mammals' },{ id: 'chihuahua', parent: 'dogs' },{ id: 'labrador', parent: 'dogs' },{ id: 'persian', parent: 'cats' },{ id: 'siamese', parent: 'cats' }];

// Create properties for the parents (their values are empty objects)
let res = Object.fromEntries(categories.map(({parent}) => [parent, {}]));
// Overwrite the properties for the parents of leaves to become arrays
categories.forEach(({id, parent}) => res[id] || (res[parent] = []));
// assign children to parent property, either as property of parent object or as array entry in it
categories.forEach(({id, parent}) => res[parent][res[id] ? id : res[parent].length] = res[id] || id);
// Extract the tree for the null-entry:
res = res.null;

console.log(res);