Dynamic Javascript Tree Structure

Question

I would like to build the hierarchy dynamically with each node created as a layer/level in the hierarchy having its own array of nodes. THIS SHOULD FORM A TREE STRUCTURE.There should be a root node, and an undefined number of nodes and levels to make up the hierarchy size. Nothing should be fixed besides the root node. I do not need to read or search the hierarchy, I need to construct it. The array should start {"name" : "A", "children" : []} and every new node as levels would be created {"name" : "A", "children" : [HERE-{"name" : "A", "children" : []}]}. In the child array, going deeper and deeper. Basically the array should have no values before the call, except maybe the root node. After the function call, the array should comprise of the required nodes of a number that may vary with every call depending on the results of a database query. Every child array will contain one or more node values. There should be a minimum of 2 node levels, including the root. It should initially be a Blank canvas, that is no predefined array values.

Solution 1

    function Tree(name,child){
        this.name = name;
        this.children = child || [];
        this.addNode = function (parent){
            this.children = parent;
        }
        this.addChild = function (parentName){
            this.children.push(new Tree(parentName));
        }
    }

    var tree = new Tree("A"); // create a tree (or a portion of a tree) with root "A" and empty children
    tree.addChild("B1");   // A -> B1
    tree.addChild("B2");   // A -> B2
    var subTree1 = new Tree("C1"); // create a sub tree
    subTree1.addChild("D1");   // C1 -> D1
    subTree1.addChild("D2");   // C1 -> D2
    tree.children[0].addNode(subTree1);   // add this sub tree under A->B1
    // Tree now is:  A--> B1
    //                      C1
    //                        D1
    //                        D2
    //                    B2
    tree.children[1].addChild("C2");
    // Tree now is:  A--> B1
    //                      C1
    //                        D1
    //                        D2
    //                    B2
    //                      C2
    //tree.children[0].addChild("C4");
    // Tree now is:  A--> B1
    //                      C1
    //                        D1
    //                        D2
    //                      C4
    //                    B2
    //                      C2    
    console.log(JSON.stringify(tree));

Output

{
  "name": "A",
  "children": [
    {
      "name": "B1",
      "children": {
        "name": "C1",
        "children": [
          {
            "name": "D1",
            "children": []
          },
          {
            "name": "D2",
            "children": []
          }
        ]
      }
    },
    {
      "name": "B2",
      "children": [
        {
          "name": "C2",
          "children": []
        }
      ]
    }
  ]
}

Solution 2

So your nodes have a name: property and a children: array property.

Databases typically store trees in tables as

node-id, parent-id, value1, ..., valueN

(you can get certain advantages if you store depth-first visit order and depth-first return order; ask in comments if you need the details).

If you make a single query and get this data into JSON, you will have something like (for your illustration),

[{id: "0", parent: "-1", name: "A2"}, {id: "1", parent: "0", name: "A3"}, 
 {id: "2", parent: "1", name: "A31"}, {id: "3", parent: "2", name: "A311"}, 
 {id: "4", parent: "2", name: "A312"}]

You can convert this into {name: children:} format with the following code:

  // data is an array in the above format
function toTree(data) {
   var childrenById = {}; // of the form id: [child-ids]
   var nodes = {};        // of the form id: {name: children: }
   var i, row;
   // first pass: build child arrays and initial node array
   for (i=0; i<data.length; i++) {
       row = data[i];
       nodes[row.id] = {name: row.name, children: []};
       if (row.parent == -1) { // assume -1 is used to mark the root's "parent"
          root = row.id; 
       } else if (childrenById[row.parent] === undefined) {
          childrenById[row.parent] = [row.id];
       } else {
          childrenById[row.parent].push(row.id);
       }
   }
   // second pass: build tree, using the awesome power of recursion!
   function expand(id) {
       if (childrenById[id] !== undefined) {
           for (var i=0; i < childrenById[id].length; i ++) {
               var childId = childrenById[id][i];
               nodes[id].children.push(expand(childId));
           }
       }
       return nodes[id];
   }
   return expand(root);
}

See http://jsfiddle.net/z6GPB/ for a working example.

Comments

[user1684586]

Do I copy your code in place of var treeData section of my code? As you can see in my code, I call the var treeData to represent the entire tree generated.

[user1684586]

Ok. But I need to maintain the name: property and a children: array property of the nodes, to achieve the tree format. Not a table format. The question was how to build this format for the nodes in a dynamic way, in that it can support any given number of nodes/levels in the hierarchy.

[user1684586]

I looks good when I use the console. I will have to integrate with my code to know if it is right. BTW thanks a lot :) Also, does your code given allow for a fixed number of nodes, as I described in my example of 4 node sets, or does the loop in your code allow for a variant amount of nodes with every processing?

[user1684586]

Thanks a lot. It works great. Now all I have to do is use it with mysql. :)

[tucuxi]

This requires nodes to be added in a particular order; if the SQL query returns children before parents, you will have to reorder the nodes before you can use addChild to build a JavaScript representation

[balafi]

not sure. You could start from the bottom (or any place). for instance: var bottom = new Tree("D1"); var higher = new Tree("C1"); higher.addNode(bottom); .. but still may not be exactly what you need