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?

Possible duplicate of [Build tree array from flat array in javascript](https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript) — k.s., May 31 '19 at 05:43
Do you always have the same depth for your JSON object? or can you also add a property in your initial object to indicate if it's the last child or not? — Pingolin, May 31 '19 at 05:45
Will it always be sorted in this manner ? parent followed by child category and so on ? — Code Maniac, May 31 '19 at 05:55
How do you define "the last nodes"? By this you mean the 3rd level of the tree or the nodes which don't have children? Also, if persian had a child and siamese didn't, what would be the expected output? — Charlie, May 31 '19 at 06:05
The current output has a uniform shape; it's easier to create (you already did it), it's easier to read, and can nest any depth easily. The expected output is not uniform, much harder to implement, and is more difficult to work with the result. It also opens up many questions about corner cases. Ie, what happens when you add `{ id: "mini-siamese", parent: "siamese" }` where `"siamese"` exists as a string in an array. Or what happens when you add `{ id: "foo", parent: null }` where there are no children with `parent = foo`? The current program does not have these problems. — Mulan, May 31 '19 at 22:40

Vikash Sadangi · Answer 1 · 2019-05-31T06:19:02.187

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.

trincot · Answer 2 · 2019-05-31T07:16:49.643

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);

This is also more efficient than the multiple traversals generated by the current suggested recursions. — גלעד ברקן, Jun 01 '19 at 13:36

Building a tree recursively in JavaScript

2 Answers2