Create a tree from JSON

Question

I am new to Javascript, I had some classes, but I still found out about it, and I was working on creating a tree from JSON. I looked at other answers here, but I just can't figure out what this reduction, recursion, and jquery thingys are. So I made my own functions.

But first, my JSON looks like this:

var data = [{ "id": 51, "name": "root" }, { "id": 54, "name": "app", "parentId": 53 }, { "id": 55, "name": "text.txt", "parentId": 54 }, { "id": 53, "name": "share", "parentId": 52 }, { "id": 52, "name": "local", "parentId": 51 }]; 

And these functions process the JSON object:

 var treeNode = function(nodeId, name) { var children = []; this.nodeId = nodeId; this.name = name; this.parentNode = null; this.setParent = function(parentNode) { this.parentNode = parentNode; }; this.addChild = function(node){ children.push(node); node.setParent(this); }; }; var Tree = function() { this.nodes = []; this.findNodeById = function(nodeId) { for (var i=0; i<this.nodes.length; i++) { if (this.nodes[i].nodeId === nodeId) { return this.nodes[i]; } } return null; }; this.createNode = function(nodeId, name, parentNode) { var node = new treeNode(nodeId, name); if (parentNode) { parentNode.addChild(node); } this.nodes.push(node); } }; function createTree(data) { var tree = new Tree(); var temp = []; for (var i=0; i<data.length; i++) { var inputNode = data[i]; var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null; tree.createNode(inputNode.id, inputNode.name, parentNode); } return tree.nodes; } 

Then I call the function: createTree (data);

So, after a lot of debugging trying to make functions, etc., I finally realized that I can make a mistake somewhere, because now the parents for the nodes for 54 and 53 are not displayed, and I just can’t wrap my head that I I'm doing it wrong and how can I fix it? Can someone help me?

Any suggestions are greatly appreciated.

Answer 1

In general, the code looks good. The problem is algorithmic.
It is directly related to the insertion order of nodes.

Cause

You have an empty tree.
First insert node # 51. Now you have a tree with one node # 51.
And then you try to insert node # 54 with parentNode # 53 ... which does not exist.

Here

 var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null; 

you call tree.findNodeById , which tree.findNodeById through your tree, cannot find node 53 (it is not already in the tree) and returns null .

So your second node gets parentNode to null instead of node # 53.

Decision

The basic idea is that you always need to make sure that for each inserted node, the parent node is already in the tree.

How to do it?

The easiest solution for your input that comes to my mind is to sort the array on parentNode in ascending order before insertion.
This ensures that you always insert child nodes after the parent node, but it only works if the nodes are numbered in a topological order .
This means that parentId always less than id . For example, node 5 cannot have a parent with identifier 7.

Here it works correctly for your input:

 var data = [{ "id": 51, "name": "root" }, { "id": 54, "name": "app", "parentId": 53 }, { "id": 55, "name": "text.txt", "parentId": 54 }, { "id": 53, "name": "share", "parentId": 52 }, { "id": 52, "name": "local", "parentId": 51 }]; var treeNode = function(nodeId, name) { var children = []; this.nodeId = nodeId; this.name = name; this.parentNode = null; this.setParent = function(parentNode) { this.parentNode = parentNode; }; this.addChild = function(node){ children.push(node); node.setParent(this); }; }; var Tree = function() { this.nodes = []; this.findNodeById = function(nodeId) { for (var i=0; i<this.nodes.length; i++) { if (this.nodes[i].nodeId === nodeId) { return this.nodes[i]; } } return null; }; this.createNode = function(nodeId, name, parentNode) { var node = new treeNode(nodeId, name); if (parentNode) { parentNode.addChild(node); } this.nodes.push(node); } }; function createTree(data) { // HERE, you sort your array by parentId ASC: data = data.sort(function(a, b) { return a.parentId - b.parentId; }); var tree = new Tree(); var temp = []; for (var i=0; i<data.length; i++) { var inputNode = data[i]; var parentNode = inputNode.parentId ? tree.findNodeById(inputNode.parentId) : null; tree.createNode(inputNode.id, inputNode.name, parentNode); } return tree.nodes; } console.log(createTree(data)); 

However, if your nodes are numbered randomly, you will need to implement topological sorting instead of just sorting by parentId .

PS

By the way, you can use a map of objects instead of an array, so as not to iterate over it every time. This will give an improvement in O(n) - O(1) instead of O(n) :

 var Tree = function() { this.nodes = {}; this.findNodeById = function(nodeId) { return nodes[nodeId]; }; this.createNode = function(nodeId, name, parentNode) { var node = new treeNode(nodeId, name); if (parentNode) { parentNode.addChild(node); } if (this.nodes[nodeId]) { throw new Error("There is already node with ID " + nodeId + " in the tree."); } this.nodes[nodeId] = node; } };