Javascript: building a hierarchical tree
<p>My data has these properties:</p>

<ol>
<li>Each entry has a unique id (Id)</li>
<li>Each has a Parent field, which points to the Id of the parent.</li>
<li>A node can have multiple children, but only one parent.</li>
</ol>

<p>My first attempt to build a tree is below. It is buggy as the recursion causes infinite loop. Even if I solve it, I am not sure is there a better approach to do this. Currently, I am doing it in 2 pass. </p>

<p>I like it to be as efficient possible as I have decent amount of data, also needs to rebuild the tree dynamically (the root can be any node)</p>

<p>There is sample data in the program below.</p>

<pre><code> arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing
</code></pre>

<p>I was hoping the output to be (it might be wrong nested structure, as I manually wrote it. but, what I am hoping is a valid json structure with node as a field 'value' and children as an array.)</p>

<pre><code>{
 "value": {"Id":"1", "Name":"abc", "Parent":""},
 "children": [
  {
   "value": {"Id":"2", "Name":"abc", "Parent":"1"},
   "children": [
    {
     "value": {"Id":"3", "Name":"abc", "Parent":"2"},
     "children": []
     },
     {
     "value": {"Id":"4", "Name":"abc", "Parent":"2"},
     "children": []
     }
   ]
..
}
</code></pre>

<p>sample program.</p>

<pre><code>function convertToHierarchy(arry, root) 
{
//root can be treated a special case, as the id is known
    arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing


    var mapping = {}; // parent : [children]
    for (var i = 0; i &lt; arry.length; i++) 
    {
        var node = arry[i];

    if (!mapping[node.Id]) { 
          mapping[node.Id] = {value: node, children:[] } ;
        }else{
      mapping[node.Id] = {value: node} //children is already set    
    }

    if (!mapping[node.Parent]) { //TODO what if parent doesn't exist.
                mapping[node.Parent] =  {value: undefined, children:[ {value: node,children:[]} ]};
        }else {//parent is already in the list
        mapping[node.Parent].children.push({value: node,children:[]} )
    }

    }
    //by now we will have an index with all nodes and their children.

    //Now, recursively add children for root element.

    var root = mapping[1]  //hardcoded for testing, but a function argument
    recurse(root, root, mapping)
    console.log(root)

    //json dump
}

function recurse(root, node, mapping)
{
    var nodeChildren = mapping[node.value.Id].children;
    root.children.push({value:node.value, children:nodeChildren})
   for (var i = 0; i &lt; nodeChildren.length; i++) {
        recurse(root, nodeChildren[i], mapping);
    }
    return root;
}
</code></pre>

<p>thank you for the help.   </p>

<h2>EDIT:</h2>

<p>I got 3 good solutions sofar, and hope the upvotes suggest more idiomatic, efficient implementation. I am not sure, utilizing the property of my data that, there will be only one root element in the set of input array, and also the root is always given, any of these implementation could be better. I should also be learning how to benchmark, as my requirement is how efficiently (fast/without much memory) the tree can be rebuild. For example, the input is already cached (arry) and rebuild the tree like</p>

<pre><code>convertToHierarchy(parentid)
....
convertToHierarchy(parentid2)
...
</code></pre>

<p>Thanks for all  your help.</p>
