Converting flat structure to hierarchical

Question

I need to create function which will be able to convert flat object to recursive object. Here is my example: I have flat array:

var flatArray = [
    {
        Description: "G",
        guid: "c8e63b35",
        parent: null,
    },
    {
        Description: "Z",
        guid: "b1113b35",
        parent: "c8e63b35",
    },
    {
        Description: "F",
        guid: "d2cc2233",
        parent: "b1113b35",
    },
    {
        Description: "L",
        guid: "a24a3b1a",
        parent: null,
    },
    {
        Description: "K",
        guid: "cd3b11caa",
        parent: "a24a3b1a",
    },      
]

the result should be:

recursiveArray = [
    {
        Description: "G",
        guid: "c8e63b35",
        parent: null,
        Children: [
            {
                Description: "Z",
                guid: "b1113b35",
                parent: "c8e63b35",
                Children: [
                    {
                        Description: "F",
                        guid: "d2cc2233",
                        parent: "b1113b35",
                    }
                ]
            }, 
        ]
    },
    {
        Description: "L",
        guid: "a24a3b1a",
        parent: null,
        Children: [
        {
            Description: "K",
            guid: "cd3b11caa",
            parent: "a24a3b1a",
        }
    }
]

Please help me find the way to do it. An worked algorithm will be appreciated, because I have problem with understand how to do this correctly. In each case I need to find a specific location for checked element in recursive structure and push it into finded element children array. I think this is stupid and inefficient. Is there any way to do this fast and efficient?

Edit: The recursive array was in wrong format. Now it should be ok. My array is not sort in any way.

Solution 1

This one works nicely and is easy to read:

function flatToHierarchy (flat) {

    var roots = [] // things without parent

    // make them accessible by guid on this map
    var all = {}

    flat.forEach(function(item) {
      all[item.guid] = item
    })

    // connect childrens to its parent, and split roots apart
    Object.keys(all).forEach(function (guid) {
        var item = all[guid]
        if (item.parent === null) {
            roots.push(item)
        } else if (item.parent in all) {
            var p = all[item.parent]
            if (!('Children' in p)) {
                p.Children = []
            }
            p.Children.push(item)
        }
    })

    // done!
    return roots
}

Solution 2

This is how I would do it:

var flatArray = [{
    Description: "G",
    guid: "c8e63b35",
    parent: null,
}, {
    Description: "Z",
    guid: "b1113b35",
    parent: "c8e63b35",
}, {
    Description: "F",
    guid: "d2cc2233",
    parent: "b1113b35",
}, {
    Description: "L",
    guid: "a24a3b1a",
    parent: null,
}, {
    Description: "K",
    guid: "cd3b11caa",
    parent: "a24a3b1a",
}];

var recursiveArray = unflatten(flatArray);

alert(JSON.stringify(recursiveArray, null, 4));

<script>
function unflatten(items) {
    return items.reduce(insert, {
        res: [],
        map: {}
    }).res;
}

function insert(obj, item) {
    var parent     = item.parent;
    var map        = obj.map;
    map[item.guid] = item;

    if (parent === null) obj.res.push(item);
    else {
        var parentItem = map[parent];

        if (parentItem.hasOwnProperty("Children"))
            parentItem.Children.push(item);
        else parentItem.Children = [item];
    }

    return obj;
}
</script>

Of course, this only works if your flatArray has the property that every parent appears before its children.

Hope that helps.

Comments

[Oka]

Shouldn't the 'L' object have 'c8e63b35' as its parent, not null?

[Adam Mrozek]

Yes, this is simple and functional. Thank you!

[Adam Mrozek]

This is very nice solution, perhaps I learn something new based on your answer. Thanks! :)

[Gaslan]

Can this code find children of children? I think this needs recursive function.

[Adam Mrozek]

@Gurkanat Yes, it works for 4 level structure. I check this before accepting this answer.

[franciscod]

yes it can! test it out! it's because the two-pass approach: first it puts everything at reach on the all object and then links things up!