How do I find the path to a deeply nested unique key in an object and assign child objects accordingly?

Question

With a given flat list:

let list = [
    {
        key: 1,
        parent: null,
    },
    {
        key: 2,
        parent: 1,
    },
    {
        key: 3,
        parent: null,
    },
    {
        key: 4,
        parent: 1,
    },
    {
        key: 5,
        parent: 2,
    }
]

How do I create a nested object like the one below?

let nest = {
    children: [
        {
            key: 1,
            children: [
                {
                    key: 2,
                    children: [
                        {
                            key: 5,
                            children: []
                        }
                    ]
                },
                {
                    key: 4,
                    children: []
                }
            ]
        },
        {
            key: 3,
            children: []
        }
    ]
}

I'm not sure how to approach this. The solution I have in mind would have to iterate over the list over and over again, to check if the object's parent is either null, in which case it gets assigned as a top-level object, or the object's parent already exists, in which case we get the path to the parent, and assign the child to that parent.

P.S. I don't think this is a duplicate of any of the below

• this checks for a key in a flat object.
• this doesn't show anything that would return a path, given a unique key.

Answer 1

For building a tree, you could use a single loop approach, by using not only the given key for building a node, but using parent as well for building a node, where the dendency is obviously.

It uses an object where all keys are usesd as reference, like

{
    1: {
        key: 1,
        children: [
            {
                /**id:4**/
                key: 2,
                children: [
                    {
                        /**id:6**/
                        key: 5,
                        children: []
                    }
                ]
            },
            {
                /**id:8**/
                key: 4,
                children: []
            }
        ]
    },
    2: /**ref:4**/,
    3: {
        key: 3,
        children: []
    },
    4: /**ref:8**/,
    5: /**ref:6**/
}

The main advantage beside the single loop is, it works with unsorted data, because of the structure to use keys and parent information together.

var list = [{ key: 1, parent: null, }, { key: 2, parent: 1, }, { key: 3, parent: null, }, { key: 4, parent: 1, }, { key: 5, parent: 2, }],
    tree = function (data, root) {
        var r = [], o = {};
        data.forEach(function (a) {
            var temp = { key: a.key };
            temp.children = o[a.key] && o[a.key].children || [];
            o[a.key] = temp;
            if (a.parent === root) {
                r.push(temp);
            } else {
                o[a.parent] = o[a.parent] || {};
                o[a.parent].children = o[a.parent].children || [];
                o[a.parent].children.push(temp);
            }
        });
        return r;
    }(list, null),
    nest = { children: tree };

console.log(nest);

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