Building a nested tree of data from plain array of objects

Question

I have an array of objects, like those ones:

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "IndustrialDesign"
  }
}

...

{
  "short_id": "2q56r",
  "path": "/2p45q/",
  "name": {
    "en-US": "Automotive"
  }
}

I must iterate over each element of the array and check the path, then find the parent of the element and push it in a new array property of that parent called sub. Each child can have a sub property on it's own, thus being a parent of more children. The final result (for this example) would look like:

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "Test A"
  },
  "sub": [
    {
      "short_id": "2q56r",
      "path": "/2p45q/",
      "name": {
        "en-US": "Test A.1"
      }
    }
  ]
}

I have a working code (using this jsonpath lib):

function(categories) {
    var _categories = [];

    angular.forEach(angular.copy(categories), function(_category) {
        if (_category.path === "/") {
            _categories.push(_category);
        } else {
            var _path = _category.path.split("/");
            _path.pop();
            var _parent = _path.pop();

            jsonpath.apply(_categories, "$..[?(@.short_id=='" + _parent + "')]", function(obj) {
                if(!obj.hasOwnProperty("sub")) {
                    obj.sub = [];
                }
                obj.sub.push(_category);
                return obj;
            });
        }
    });

    return _categories;
}

but the performance is really bad, mainly because I'm querying the entire array for each iteration.

My question is how can I optimize my code?

Notes:

• Each short_id is exactly 5 characters long.
• Each character in short_id can be [0-9a-z]
• path is guaranteed to start and end with a /

Answer 1

Create another tmp object as Hashmap, so you can just use path and id to create a new key to store.

Logic :

1. If path is '/', its root, put to the _categories array.

2. If not, check if the target parent is exist in the hashStore or not, if not, create a fake one, and put it self to target is sub attr.

3. For all element, create a key by _category.path + _category.short_id + '/', and check if its exist in the hashStore, if exist, the one in store should be a fake, get sub from fake. Then assign itself to the hashStore by created key.

Use a key to decide whether the object exist in the map or not should be O(1). So the performance of the this function should be O(n) while n is the number of element in origin list.

function buildTree(categories) {
  var _categories = [];
  var store = {};

  angular.forEach(angular.copy(categories), function(_category) {
    if (_category.path === '/') {
      _categories.push(_category);
    } else {
      var target;
      // If parent exist
      if (typeof store[_category.path] !== 'undefined') {

        // Check parent have sub or not, if not, create one.
        target = store[_category.path];
        if (typeof store[_category.path].sub === 'undefined') {
          target.sub = [];
        }

      } else {
        // Create fake parent.
        target = {sub: []};
        store[_category.path] = target;
      }

      // Push to parent's sub
      target.sub.push(_category);
    }

    // Create key map
    var key = _category.path + _category.short_id + '/';
    // If fake object exist, get its sub;
    if (typeof store[key] !== 'undefined') {
      _category.sub = store[key].sub;
    }
    store[key] = _category;

  });

  return _categories;
}