Q:

Building nested lists from ancestor data?

Given the structure:
{
    id: 'id-1',
    name: 'name1',
    ancestors: []
},{
    id: 'id-2',
    name: 'name2',
    ancestors: []
},{
    id: 'id-3',
    name: 'name3',
    ancestors: ['id-1']
},{
    id: 'id-4',
    name: 'name4',
    ancestors: ['id-3', 'id-1']
}

Assume they are not sorted in any meaningful way.
The ancestors field is an array showing the path up to top level.

What would be the most efficient way to build nested lists (ul)?
My first thought is a recursive approach, but that seems troublesome as it would repeatedly search the entire list.  Since this will be a javascript solution running in the browser that could be problematic.

A:

You could build a tree and then render a nested list.

function getTree(data) {
    var o = {};
    data.forEach(function (a) {
        var parent = a.ancestors[0];
        if (o[a.id] && o[a.id].children) {
            a.children = o[a.id].children;
        }
        o[a.id] = a;
        o[parent] = o[parent] || {};
        o[parent].children = o[parent].children || [];
        o[parent].children.push(a);
    });
    return o.undefined.children;
}

function buildList(tree, target) {
    var ul = document.createElement('ul');
    tree.forEach(o => {
        var li = document.createElement('li');
        li.appendChild(document.createTextNode(o.name));
        buildList(o.children || [], li);
        ul.appendChild(li);
    });
    target.appendChild(ul);
}

var data = [{ id: 'id-1', name: 'name1', ancestors: [] }, { id: 'id-2', name: 'name2', ancestors: [] }, { id: 'id-3', name: 'name3', ancestors: ['id-1'] }, { id: 'id-4', name: 'name4', ancestors: ['id-3', 'id-1'] }],
    tree = getTree(data);

console.log(tree);
buildList(tree, document.body);

