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.

Answer 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
}