JavaScript function for to find a defined element within a nested array

Question

Following task: You've got an array which contains parts. Parts can contain subparts. Subparts can contain further subparts and so on.

For example:

computer 
 cpu
 hardDisc
 graphicsCard
 graphicsCardCpu
 graphicsCardRam

Let's suppose I have a correct structure where every part has a unique id. Such a structure would be assured.

I've made this function which retrieves a part with a given id from the above described structure.

// Example structure
var structure = [
 {
 id : 1,
 name : 'firstLevelOne',
 category : 'alpha',
 subParts : null,
 },
 {
 id : 2,
 name : 'firstLevelTwo',
 category : 'beta',
 subParts : [{
 id : 6,
 name : 'secondLevelOne',
 category : 'alpha',
 subParts : null
 }],
 },
 {
 id : 3,
 name : 'firstLevelThree',
 category : 'alpha',
 subParts : [{
 id : 7,
 name : 'secondLevelTwo',
 category : 'gamma',
 subParts : [{
 id : 8,
 name : 'thirdLevelOne',
 category : 'beta',
 subParts : [ {
 id: 11,
 name : 'fourthLevelOne',
 category : 'alpha',
 subParts : null
 }]
 },
 {
 id : 10,
 name : 'secondLevelFour',
 category : 'beta',
 subParts : null
 }]
 }],
 },
 {
 id : 4,
 name : 'firstLevelFour',
 category : 'gamma',
 subParts : [{
 id : 9,
 name : 'secondLevelThree',
 category : 'alpha',
 subParts : null
 }],
 },
 {
 id : 5,
 name : 'firstLevelFive',
 category : 'beta',
 subParts : null,
 }
]; 
// #### Let's try this out ...
var part = getPart(4, structure);
for (var i in part) {
 console.log(part[i]);
} 
console.log('\n');
part = getPart(11, structure);
for (var i in part) {
 console.log(part[i]);
}
console.log('\n');
part = getPart(8, structure);
for (var i in part) {
 console.log(part[i]);
} 
// ############################
// The actual function ...
// Retrieves the object from 
// the storage-array.
function getPart(id, arr) {
 var ret = null;
 var i;
 if (!id || !arr) return ret;
 for (i = 0; i < arr.length; i++) {
 if (arr[i]['id'] === id) {
 return arr[i];
 } else {
 if (arr[i]['subParts']) {
 ret = getPart(id, arr[i]['subParts']);
 if (ret) return ret;
 } 
 }
 };
 return ret;
}

Are there weak points? Could the function be improved?

Answer 1

Your function is fine for me according to the structure you mentioned. But it's slow because it has to run a full search every time it's called. The main reason is the structure. So I would suggest that build an index which will help you to search quicker.

Building an index

An index is simply a map associating each id to the corresponding Part. You will only need to fill it once then use it to access Parts by id more quickly.

var index = {};
fillIndexFrom(index, structure);
function buildIndexFrom (index, list) {
 list.forEach(function(part) {
 index[part.id] = part;
 if (part.subParts)
 fillIndexFrom(index, part.subParts);
 });
}
// Then to get the part of id 4 for example you simply do
var part = index[4];

Complexity comparison

If we assume that there are N parts and that you will do M searches then:

• Your initial solution will cost O(M*N) (every search costs O(N) in worst case)
• The index solution will cost O(N) + M * O(logN) (O(N) to fill the index and then O(logN) for every search)