Reorder a JS object in a child-parent structure

Question

I'm facing a brain-breaker (at leats for me) : I get a json file with a one depth array of data objects like this:

[
{"id":1, "name":"Sport", "parent_id":0, "children":[]},
{"id":2, "name":"Tennis", "parent_id":4, "children":[]},
{"id":3, "name":"Climbing", "parent_id":5, "children":[]},
{"id":4, "name":"Indoor", "parent_id":1, "children":[]},
{"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
{"id":6, "name":"Bowling", "parent_id":4, "children":[]}
]

how can I convert this in a tree-structure where children are put inside their parent's children array? objects are not always in te right order, a child can come before its parent in the array. (like id 2 and 3 in my example)

This is how I need it in the end:

[
{"id":1, "name":"Sport", "parent_id":0, "children":
  [
    {"id":4, "name":"Indoor", "parent_id":1, "children":
    [
      {"id":2, "name":"Tennis", "parent_id":4, "children":[]},
      {"id":6, "name":"Bowling", "parent_id":4, "children":[]},
    ]},
    {"id":5, "name":"Outdoor", "parent_id":1, "children":
    [
      {"id":3, "name":"Climbing", "parent_id":5, "children":[]}
    ]},
  ]}
]

Any idea how to achieve this?

I tried iterating over the elements and pushing the inside their parents children array, but when a parent has been moved, the next sibling can't find the parent anymore...

Answer 1

I'm not sure why everyone is so keen on writing inefficient O² algorithms (nested for-loops), but here is one in O(n log n) time:

function treeify(nodes) {
    var indexed_nodes = {}, tree_roots = [];
    for (var i = 0; i < nodes.length; i += 1) {
        indexed_nodes[nodes[i].id] = nodes[i];
    }
    for (var i = 0; i < nodes.length; i += 1) {
        var parent_id = nodes[i].parent_id;
        if (parent_id === 0) {
            tree_roots.push(nodes[i]);
        } else {
            indexed_nodes[parent_id].children.push(nodes[i]);
        }
    }
    return tree_roots;
}

var nodes = [
    {"id":1, "name":"Sport", "parent_id":0, "children":[]},
    {"id":2, "name":"Tennis", "parent_id":4, "children":[]},
    {"id":3, "name":"Climbing", "parent_id":5, "children":[]},
    {"id":4, "name":"Indoor", "parent_id":1, "children":[]},
    {"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
    {"id":6, "name":"Bowling", "parent_id":4, "children":[]}
];

console.log(JSON.stringify(treeify(nodes), undefined, "\t"));

Answer 2

This should do http://jsfiddle.net/arPgr/

var arr = [
{"id":1, "name":"Sport", "parent_id":0, "children":[]},
{"id":2, "name":"Tennis", "parent_id":4, "children":[]},
{"id":3, "name":"Climbing", "parent_id":5, "children":[]},
{"id":4, "name":"Indoor", "parent_id":1, "children":[]},
{"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
{"id":6, "name":"Bowling", "parent_id":4, "children":[]}
]

var i = 0, len = arr.length, item, parent, id, key, treeArr = {};

for (; i < len; i++) {
    item = arr[i];
    parent = item.parent_id;
    id = item.id;

    if (treeArr[id] == undefined) {
       treeArr[id] = item;   
    } else if (typeof treeArr[id] == 'object') {
        for (key in item) {
            if (key == 'children') continue;
            treeArr[id][key] = item[key];   
        }        
    }

    if (typeof treeArr[parent] != 'object') {
        treeArr[parent] = { children: [] };   
    }

    treeArr[parent].children.push(treeArr[id]);
}

console.log(treeArr[0]);