Convert a flat defined tree to a depth tree, JavaScript

Question

For an input flat tree:

let input = [{
        levelId: '1'
    }, {
        levelId: '1.1'
    }, {
        levelId: '1.1.1'
    }, {
        levelId: '1.2'
    }, {
        levelId: '2'
    }, {
        levelId: '2.1.1'
    }
]

What would be the best way to convert that into multi-level tree, where levelId defines the level of the tree:

let output = [{
        levelId: '1',
        children: [{
                levelId: '1.1',
                children: [{
                        levelId: '1.1.1'
                    }
                ]
            }
        ]
    }, {
        levelId: '2',
        children: [{
                levelId: '2.1.1'
            }
        ]
    }
]

Lodash is used.

Answer 1

I first sort the array according the object level, then I create an intermediate object for mapping each level id with the object itself and find its parent from the intermediate object. Then I output an array with object that has no parent.

Hope this help.

var input = [
  {
	levelId: '1'
  },
  {
	levelId: '1.1'
  },
 {
	levelId: '1.1.1'
  },
  {
	levelId: '1.2'
  },
  {
	levelId: '2'
  }, 
  {
	levelId: '2.1.1'
  },
  {
	levelId: '3.1'
  },
  {
	levelId: '3.1.1'
  }
];


function exec(input){

	var temp = {};
	
	//Sort the array by level then create an intermediate object that map level id with the level object and map with its parent
	input.sort((a,b) => a.levelId.split(".").length - b.levelId.split(".").length).forEach( lvl => {
		temp[lvl.levelId] = lvl;
		
		if(lvl.levelId.indexOf('.') !== -1){
			var parentLevelId = lvl.levelId;
			var parent = undefined;
			//Search parent level by level (ie. 3.1.1 -> 3.1 -> 3)
			do{
				if(parentLevelId.indexOf('.') === -1) break;
				parentLevelId = parentLevelId.substr(0, parentLevelId.lastIndexOf("."));
				parent = temp[parentLevelId];
			}while(typeof parent === 'undefined')
			
			if(typeof parent !== 'undefined'){
				if(typeof parent.children === 'undefined'){
					parent.children = [];
				}
				parent.children.push(lvl);
				lvl.parent = parent;
			}
		}
	});
	
	
	//push the root object (level object that has no parent) to an output array
	var output = [];
	for(var key in temp){
		if(typeof temp[key].parent !== 'undefined'){
			delete temp[key]["parent"];
		}else{
			output.push(temp[key]);
		}
	}

	return output;

}


console.log(JSON.stringify(exec(input), 0, 3));