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)