Tree from an associative array

Question

There is an array:

let docs = [      
    { "_id":"1", parent:"_", "title":"one"},
    { "_id":"2", parent:"1", "title":"two"},
    { "_id":"4", parent:"_", "title":"title"},
    { "_id":"5", parent:"4", "title":"www"},
    {"_id":"_", "name":"root" },
];

I need to get out of it that's a tree:

{'_id':'_','name':'root','child':
    [
        {'_id':'1','parent':'_','title':'one','child':
            [
                {'_id':'2','parent':'1','title':'two','child':[]}
            ]
        },
        {'_id':'4','parent':'_','title':'title','child':
            [
                {'_id':'6','parent':'4','title':'vvv','child':[]}
            ]
        }
    ]
}

But my code only works if the parent element is always higher on the list than the children, and I want to make that work universally.

This is code:

let node = {};
for (let doc of docs) {      
    doc.child = [];
    node[doc._id] = doc;

    if (typeof doc.parent === "undefined")
        tree = doc;
    else 
        node[doc.parent].child.push(doc);
}

console.log('tree->', JSON.stringify(tree)); 

code on codepen: http://codepen.io/alex183/pen/OWvrPG?editors=0112

Answer 1

This is a proposal with Array#reduce and Map. It sorts the array in advance.

var docs = [{ _id: "1", parent: "_", title: "one" }, { _id: "2", parent: "1", title: "two" }, { _id: "4", parent: "_", title: "title" }, { _id: "5", parent: "4", title: "www" }, { _id: "_", name: "root" }],
    order = { undefined: -2, _: -1 },
    tree = docs
        .sort((a, b) => (order[a.parent] || a.parent) - (order[b.parent] || b.parent) || a._id - b._id)
        .reduce(
            (m, a) => (
                m
                    .get(a.parent)
                    .push(Object.assign({}, a, { child: m.set(a._id, []).get(a._id) })),
                m
            ),
            new Map([[undefined, []]])
        )
        .get(undefined);

console.log(tree);

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

Answer 2

The quick and dirty way is to use a sort function.

docs = docs.sort((a, b) => (a._id - b._id));