CODEWITHSUNDEEP
javascript
Parth Patel
Parth Patel

Reputation: 197

Flat Structure to Tree Structure

I have gone through the answers already given on this topic but I am not able to get the desired output. Hence, I am asking this question again.

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = {};
var parentCache = {};
// for each element definition in the data array
for (var i = 0; i < data.length; i++) {
    var element = data[i];
    var Title = element.Title;
   

    // create a new object and initialize
    var newObj = {"Title" : Title};
        newObj["children"] = [];

    // put this object into its parent
    if (element.Parent === "root") {
        root[Title] = newObj;
    } else {
        // XXX - if the parent isn't defined first this will fail      
        var parent = parentCache[element.Parent];      
        parent.children.push(newObj); 
      //need to run a loop on 'root' to push at different nodes, how?
    }
    // store this object in case it is a parent
    parentCache[Title] = newObj;
}

document.write('<pre>' + JSON.stringify(root, 0, 4) + '</pre>');
// console.log(JSON.stringify(root));

JSBIN link for code

I am not able to push Table 1 under Report 2 --> View 1 and all further nodes, if there is any View 1 object will be present in the root object. How to solve this?

Upvotes: 0

Views: 104

Answers (1)

Wyck
Wyck

Reputation: 11740

Probably the easiest way to understand this is to turn each of your data objects into a tree node with an additional children: [] array. Then add each node as a child of any nodes that claim to have a Title matching what the child says is its Parent. This will, of course, potentially add the child multiple places into the tree, (Parent is not unique) but I believe that is what you want. I will do this with no algorithmic optimization, just to keep it simple so that you understand the fix.

Recognizing the fact that the parent is not unique should have steered you away from your approach of constructing a parentCache. There may be multiple nodes that qualify to be the parent of any given node. In fact, any object that has the right Title, will be such a parent.

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = { Title: "root", children: [] };
var parentCache = {};

// Put a root node into the tree
var nodes = data.map((e) => {
 return { Title: e.Title, Parent: e.Parent, children: [] };
 });
nodes.push(root);

// Brute force: add each node as a child of its parent.
for (var iChild = 0; iChild < nodes.length; ++iChild) {
  for (var iParent = 0; iParent < nodes.length; ++iParent) {
    if (nodes[iParent].Title == nodes[iChild].Parent) {
       nodes[iParent].children.push(nodes[iChild]);
    }
  }
}

document.write('<pre>' + JSON.stringify(root, 0, 4) + '</pre>');
// console.log(JSON.stringify(root));

If you wanted to optimize this, you could still construct a parent cache, but each entry in the cache would be a list of all elements that have the matching title string. Then, you would iterate over each element and add it as a child of all its parents. This would take the search time for the parent down to O(1) instead of O(N). But the example I'm posting will use the O(N^2) approach because it's easier to understand what your original problem was.

Edit: Indexed solution

At the request of @alQemist, I have added a version of the solution that uses an index to allow locating the parent node in constant time.

var data = [

{ Title : "Report 1" , Parent : "root"} ,
{ Title : "Report 2" , Parent : "root"} ,
{ Title : "Report 3" , Parent : "root"} ,
{ Title : "View 1" , Parent : "Report 1"} ,
{ Title : "View 2" , Parent : "Report 1"} ,
{ Title : "Table 1" , Parent : "View 1"} ,
{ Title : "Table 2" , Parent : "View 1"} ,
{ Title : "Table 3" , Parent : "View 1"} ,
{ Title : "SLT" , Parent : "Table 1"} ,
{ Title : "SRS" , Parent : "Table 2"} ,
{ Title : "INFORMATICA" , Parent : "Table 3"} ,
{ Title : "Table 3" , Parent : "View 2"} ,
{ Title : "Table 4" , Parent : "View 2"} ,
{ Title : "Table 5" , Parent : "View 2"} ,
{ Title : "SLT" , Parent : "Table 4"} ,
{ Title : "SLT" , Parent : "Table 5"} ,
{ Title : "View 1" , Parent : "Report 2"} ,
{ Title : "View 3" , Parent : "Report 2"} ,
{ Title : "View 4" , Parent : "Report 2"} ,
{ Title : "Table 6" , Parent : "View 3"} ,
{ Title : "Table 7" , Parent : "View 3"} ,
{ Title : "Table 3" , Parent : "View 3"} ,
{ Title : "Table 8" , Parent : "View 4"} ,
{ Title : "Table 9" , Parent : "View 4"} ,
{ Title : "Table 10" , Parent : "View 4"} ,
{ Title : "SLT" , Parent : "Table 6"} ,
{ Title : "SRS" , Parent : "Table 7"} ,
{ Title : "INFORMATICA" , Parent : "Table 8"} ,
{ Title : "SLT" , Parent : "Table 9"} ,
{ Title : "SRS" , Parent : "Table 10"} ,
{ Title : "View 5" , Parent : "Report 3"} ,
{ Title : "View 6" , Parent : "Report 3"} ,
{ Title : "View 7" , Parent : "Report 3"} ,
{ Title : "View 8" , Parent : "Report 3"} ,
{ Title : "Table 11" , Parent : "View 5"} ,
{ Title : "Table 12" , Parent : "View 5"} ,
{ Title : "Table 13" , Parent : "View 5"} ,
{ Title : "Table 14" , Parent : "View 5"} ,
{ Title : "Table 15" , Parent : "View 6"} ,
{ Title : "Table 16" , Parent : "View 6"} ,
{ Title : "Table 17" , Parent : "View 6"} ,
{ Title : "Table 18" , Parent : "View 6"} ,
{ Title : "Table 19" , Parent : "View 7"} ,
{ Title : "Table 20" , Parent : "View 7"} ,
{ Title : "Table 21" , Parent : "View 8"} ,
{ Title : "Table 22" , Parent : "View 8"} ,
{ Title : "Table 23" , Parent : "View 8"} ,
{ Title : "SLT" , Parent : "Table 11"} ,
{ Title : "SRS" , Parent : "Table 12"} ,
{ Title : "INFORMATICA" , Parent : "Table 13"} ,
{ Title : "SLT" , Parent : "Table 14"} ,
{ Title : "SRS" , Parent : "Table 15"} ,
{ Title : "INFORMATICA" , Parent : "Table 16"} ,
{ Title : "SLT" , Parent : "Table 17"} ,
{ Title : "SRS" , Parent : "Table 18"} ,
{ Title : "INFORMATICA" , Parent : "Table 19"} ,
{ Title : "SLT" , Parent : "Table 20"} ,
{ Title : "SRS" , Parent : "Table 21"} ,
{ Title : "INFORMATICA" , Parent : "Table 22"} ,
{ Title : "INFORMATICA" , Parent : "Table 23"} ,
];

var root = { Title: "root", parents: [], children: [] };

// Put a root node into the tree
var nodes = data.map((e) => {
 return { Title: e.Title, Parent: e.Parent, parents: [], children: [] };
 });
nodes.push(root);

// construct a title index
let titleIndex = {};
nodes.forEach(n => {
  titleIndex[n.Title] = n;
});

document.write('<h1>The Index</h1><pre>' + JSON.stringify(titleIndex, 0, 4) + '</pre>');

// Each node will have a list of its parents.  Locate each parent with the index.
nodes.forEach(n => {
  if (n.Parent)
    n.parents.push(titleIndex[n.Parent]);
});

// Push each node as a child of all its parents.  Delete the parents list to avoid circular JSON.
nodes.forEach(n => {
  n.parents.forEach(p => {
    p.children.push(n);
  });
  delete n.parents;
});

document.write('<h1>The Tree</h1><pre>' + JSON.stringify(root, 0, 4) + '</pre>');

Upvotes: 2

Related Questions