How to generate parent/child nest on client side?

Question

I've searched through the myriad parent/child array/object/whatever questions here and elsewhere and haven't been able to solve my issue. I know this is a bit long, but I wanted to ensure I'm providing enough info to you guys.

Here's what I want to do:

1. I have a number of <div>-delineated items on the page with parent/child relationships, generated via php from my database
2. I want to use these items as the data source for a D3.js Dendrogram (a node-link tree diagram http://mbostock.github.com/d3/ex/cluster.html)
3. I'm storing them with left/right nested set values but also parentID values, so I can add ID, parentID, rgt, lft and depth attributes to the <div> elements, so I should have available whatever's needed to generate the parent/child relationships on the client side
4. For various reasons, instead of creating a JSON file on the server side to use as the data source, I need to create it on the client side based on the attributes in #3
5. I've had difficulty getting various suggested javascript functions to work and all the D3 examples I've found use either a preexisting JSON file or generated math-based file, not attributes of elements already on the page

Here is an example of what already works for me with the D3 Dendrogram, but it's not generated dynamically:

var tree3 = 
{"sid": "1", "children": [
    {"sid": "2", "children": [
        {"sid": "5", "children": [
            {"sid": "75"},
            {"sid": "85", "children": [
                {"sid": "87"}, ...

To give you an idea of where these attributes are in the DOM, I originally tried the below, but of course it doesn't generate any hierarchy:

function tree() {
    var tree=[];
    $("article").each(function(){
        tree.push({
            sid:$(this).attr("sid"), 
            l:$(this).attr("l"), 
            r:$(this).attr("r"),
            pid:$(this).attr("pid")
        });
    });
    return tree;
}

I've been messing around unsuccessfully with variants of the below to get a nested array:

function tree2() {
   $("article").(function(d) {
       return d.parent().attr("pid") === 0;
}, function(parent, child) {
    return parent.attr("pid") === child.parent().attr("sid");
}).toArray();
}

So, I'm driving myself crazy trying to create the javascript array nested correctly, but it's dawned on me that I may not need to and that D3's data selectors and methods could be sufficient. Could you please help me with the code to:

1. Pull the needed attributes to generate the parent/child relationship within a D3 function ("sid" is the identifier) or, if this isn't possible,
2. Create the needed array or array-like object in javascript for use by D3 (still with "sid" as the identifier).

Thanks in advance.

Answer 1

You need to get recursive! Basically the trick is to pass the current parent in as you go, which changes the context and allows you to walk down the tree.

Update: Working fiddle.

Assuming your HTML structure is something like this:

<div sid="1" pid="">
    <div sid="1.1" pid="1">
        <div sid="1.1.1" pid="1.1">
        </div>
    </div>
</div>

You could do something like this:

var _json = {};

function addTreeNode(div, parentObj) {

    var childObj = {
        sid: $(div).attr("sid"),
        pid: $(div).attr("pid")
    }

    // add this to it's parent in the JSON hierarchy
    if (!parentObj.children) parentObj.children = [];
    parentObj.children.push(childObj);

    // keep adding for all children div's
    $(div).find("div").each(function() {
        addTreeNode(this, childObj);
    });
}

// start at the roots, it will magically work it's way out to the leaves
$("body > div").each(function(){
    addTreeNode(this, _json);
});

console.log(_json);

Note that if your tree is big enough, you will cause stack overflows, especially in IE. In that case, you'll need to switch this over from recursion to iteration. It's not as pretty that way, though.