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.

can you do something like: `var recoursiveArray = []; recoursiveArray.push(flatArray[0]); recoursiveArray[0].children = []; recoursiveArray[0].children.push(flatArray[1]);` — Dima Gimburg, Jul 13 '15 at 12:51
Shouldn't the `'L'` object have `'c8e63b35'` as its parent, not `null`? — Oka, Jul 13 '15 at 12:57
@franciscod no, my array is unsorted and this is a partial problem — Adam Mrozek, Jul 13 '15 at 13:03
@DimaGimburg I can but I need to do this automatically, the structures to convert will be huge — Adam Mrozek, Jul 13 '15 at 13:04
There is a similar discussion here http://stackoverflow.com/questions/15376251/hierarchical-json-from-flat-with-parent-id-using-javascript — Dickens A S, Jul 13 '15 at 13:07

score 22 · Accepted Answer · answered Jul 13 '15 at 13:23

22

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
}

answered Jul 13 '15 at 13:23

franciscod

992
4
17

1

Yes, this is simple and functional. Thank you! – Adam Mrozek Jul 13 '15 at 13:36
Can this code find children of children? I think this needs recursive function. – Gaslan Jul 13 '15 at 13:56
1

@Gurkanat Yes, it works for 4 level structure. I check this before accepting this answer. – Adam Mrozek Jul 13 '15 at 14:00
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! – franciscod Jul 13 '15 at 14:00

Aadit M Shah · Answer 2 · 2015-07-13T13:28:41.267

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.

This is very nice solution, perhaps I learn something new based on your answer. Thanks! :) — Adam Mrozek, Jul 13 '15 at 13:37

score 0 · Answer 3 · answered Jul 13 '15 at 13:04

I tried to write the algorithm in pseudocode, ended up with JS code that almost works (perhaps some additional validations/checks are needed) but shows the general approach to the problem.

//Lets separate children (nodes with a parent) from roots (nodes without a parent)
var children = flatArray.filter(function(object){
    return object.parent !== null;
});

var roots = flatArray.filter(function(object){
    return object.parent === null;
});

//And add each child to the nodes tree
children.foreach(function(child){
    recursiveAdd(roots, child);
});

//To add a children node, node tree is searched recursively for a parent
function recursiveAdd(nodes, child){
    nodes.foreach(function(parent){
        if(parent.guid === child.parent){
            parent.Children = parent.Children | [];
            parent.Children.add(child);
        } else if(parent.Children) {
            recursiveAdd(parent.Children, child);
        }
    });
}

//Temporary children array can be garbage collected
children = null;
//Resulting node tree
var recursiveArray = roots;

score 0 · Answer 4 · answered Jul 13 '15 at 13:09

This recursive function can be good for you:

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




for (var i = 0; i < flatArray.length; i++) {
  recursive(flatArray[i]);
}


function recursive(a) {
  for (var i = 0; i < flatArray.length; i++) {
    if (flatArray[i].parent == a.guid) {
      var b = flatArray[i];
      recursive(b);
      a.Children.push(b);
    }
  }
}


console.log(flatArray)

score 0 · Answer 5 · answered Jul 13 '15 at 13:21

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",
    },      
];

//for printing
function htmlPrint(obj) {
  document.write('<pre>'+JSON.stringify(obj,null,2)+'</pre>');
};

var guids = {};
var roots = [];

flatArray.forEach(function(node){ 
  guids[node.guid] = node;       //save into a hash
  node.Children = [];            //make sure it has a children array
  //save it as root if it is a root
  if(node.parent === null){ roots.push(node);}
});
flatArray.forEach(function(node){ 
  //if it has a parent, add self to parent's children
  var parent = guids[node.parent]; 
  if(parent)  parent.Children.push(node); 
});
htmlPrint(roots);

Reza Jenabi · Answer 6 · 2020-11-08T13:22:07.177

you can use bellow code in Angular.

flatToHierarchy(flat: any[], parent: any = null, Key: string = 'id', parentKey: string = 'parentId') {
  var leafs: any = [];

  if (!parent) {
    leafs = flat.filter((x: { [x: string]: any; }) => x[parentKey] === null);
  } else {
    leafs = flat.filter((x: { [x: string]: any; }) => x[parentKey] === parent[Key]);
  }

  if (!leafs || leafs.length == 0) {
    return;
  } else {
      leafs.forEach((item: { children: any[]; }) => {
      item.children = [];
      item.children = this.flatToHierarchy(flat, item);
    });
  }
  return leafs;
}

use same like this

 this.flatToHierarchy(flatItems);

Converting flat structure to hierarchical

6 Answers6

Linked