A JSON recursive tree in JavaScript

Question

I need some help with code in JavaScript. My goal is to write a program which will allow generating a huge binary tree.

Before compilation I specify how many levels of the tree I want, assuming that every object has two children (except the last level).

Simple visualization for levels=3:

Every object has:

-Name - The first field from the shema. Also it should include information about object number,

-Type - The second field from the shema. Information about the depth of the object,

-Properties - Some static information about an object. In my situation it is the same and it is presented below,

-Children.

I wrote some code which accurately reproduces the tree form the schema:

var levels = 3; //2^0, 2^1, 2^2
var level_description = [];

for (var i = 0; i < levels; i++) {
    obj = {};
    obj.level = i;
    obj.amount = Math.pow(2, i);
    obj.indexes = [];
    if (i === 0) {
        obj.indexes[0] = 0;
        level_description.push(obj);
    } else {
        for (var j = 0; j < obj.amount; j++) {
            obj.indexes[j] = obj.amount + j - 1;
        }
        level_description.push(obj);
    }
}

console.log(level_description);

var properties = [{
    "name": "trend",
    "value": "true"
}, {
    "name": "unit",
    "value": "g"
}];

var jsonString = JSON.stringify([{
    "name": "Object_" + level_description[0].indexes[0].toString(), //Object_0
    "type": "level_" + level_description[0].level.toString(), //level_0,
    "properties": properties,
    "children": [{
        "name": "Object_" + level_description[1].indexes[0].toString(), //Object_1
        "type": "level_"  + level_description[1].level.toString(), //level_1,
        "properties": properties,
        "children": [{
            "name": "Object_" + level_description[2].indexes[0].toString(), //Object_3
            "type": "level_" + level_description[2].level.toString(), //level_2,
            "properties": properties,
            "children": []
        }, {
            "name": "Object_" + level_description[2].indexes[1].toString(), //Object_4
            "type": "level_" + level_description[2].level.toString(), //level_2,
            "properties": properties,
            "children": []
        }]
    }, {
        "name": "Object_" + level_description[1].indexes[1].toString(), //Object_2
        "type": "level_" + level_description[1].level.toString(), //level_1,
        "properties": properties,
        "children": [{
            "name": "Object_" + level_description[2].indexes[2].toString(), //Object_5
            "type": "level_" + level_description[2].level.toString(), //level_2,
            "properties": properties,
            "children": []
        }, {
            "name": "Object_" + level_description[2].indexes[3].toString(), //Object_6
            "type": "level_" + level_description[2].level.toString(), //level_2,
            "properties": properties,
            "children": []
        }]
    }]
}]);

pm.globals.set('jsonString', jsonString);

But now I am stuck. I have trouble with making it recursive and flexible.

I uploaded an output (json tree) on my google disc: https://drive.google.com/drive/folders/1__nR-AXK7uKRBT4hZtiSWetyaobk72CX?usp=sharing

Thanks for any kind of help.

Answer 1

I would suggest this solution:

var cnt = -1;
var properties = {"prop1":"a","prop2":"b"};
var MAX_LEVELS = 3;

function addNode(parent, level){
  cnt = cnt + 1;
  var node = {
    "name": "Object_" + cnt,
    "type": "level_"  + level,
    "properties": properties,
    "children": []
  };

  if (level < MAX_LEVELS){
    addNode(node, level + 1);
    addNode(node, level + 1);
  }

  if (parent){
    parent.children.push(node);
  }
  else {
    return node;
  }
}
let result = addNode(null, 0);
console.log(JSON.stringify(result, null, 4))

Answer 2

Recursive TreeNode generator

I'm not particularly fond of this implementation as it does not maintain your TreeNode numbering system (Breadth-first) as recursive functions are by nature Depth-first so a simpler and probably better implementation would be to run a couple of for loops, one for iterating every level and another for the level's required nodes. Nonetheless here's the recursive code:

function TreeNode(name, level, properties, children) {
  this.name = name;
  this.level = level;
  this.properties = properties;
  this.children = children;
}
var levels = 3; //2^0, 2^1, 2^2
var tree = new TreeNode("root", 0, {}, []);
var tempIndex = 0;

function generateArbitraryLevels(parent, levelsRemaining) {
  // last level
  if(levelsRemaining == 0) return;
  
  var currentLevel = parent.level + 1;
  
  parent.children.push(
    new TreeNode("Object_" + tempIndex++, currentLevel, {}, [])
  );
  generateArbitraryLevels(parent.children[0], levelsRemaining - 1);

  parent.children.push(
    new TreeNode("Object_" + tempIndex++, currentLevel, {}, [])
  );
  generateArbitraryLevels(parent.children[1], levelsRemaining - 1);
  
}

generateArbitraryLevels(tree, levels);
console.log(tree);

---

Previous answer (recursive-tree)

So my approach for this kind of problems is to instantiate every node in the tree individually, and after that relate them to each other.

Check out this example:

function TreeNode(name, type, properties, children) {
  this.name = name;
  this.type = type;
  this.properties = properties;
  this.children = children;
}

var obj1 = new TreeNode("Object_1", "level_0", {a: 1}, []);
var obj2 = new TreeNode("Object_2", "level_1", {a: 1}, []);
var obj3 = new TreeNode("Object_3", "level_1", {a: 1}, []);
var obj4 = new TreeNode("Object_4", "level_2", {a: 1}, []);
var obj5 = new TreeNode("Object_5", "level_2", {a: 1}, []);

/* TREE:
         1
        / \
       2   3
      / \
     4   5
*/


// push first level
obj1.children.push(obj2);
obj1.children.push(obj3);

// push second level
obj2.children.push(obj4);
obj2.children.push(obj5);



// Now suppose you want to "make it recursive"
// instead of number 2 having 5 as a child we are going to swap that out for 1

/* NEW TREE:
         1
        / \
       2   3
      / \
     4   1
        / \
       ..  ..
*/
// remove 5
obj2.children.pop();
// push 1
obj2.children.push(obj1);

Object variables are just references to the actual object in memory so in the code above obj1 === obj2.children[1] is true

Of course this is just an example, for more dynamism you should store a map (nodeKey -> node) and access the nodes through that.

Hope it helped

Answer 3

recursive tree exemple :

function makeTree(niv, max) {
	if (max === undefined) {
 		max = niv;
  }

  let obj =  {
    name: `n${max - niv}`,
    childrens:[]
  };
  
  if (niv < 1) {
  	return obj;
  }
  
  let c1 = makeTree(niv -1, max);
  obj.childrens.push(c1);
  
  let c2 = makeTree(niv -1, max);
  obj.childrens.push(c2);
 
 	return obj;
}

console.log(makeTree(4));