Databases
StackOverflow2013
Postsdbo
POJavascript: building a hierarchical tree
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJavascript: building a hierarchical tree
    text
    copied!<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>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload