Find a nested property in an object [closed]

Question

This works fine and returns an object from a nested "structure" by Id.

I would like to know if you could suggest a better approach, possible a faster one.

<script>
var data = {
    item: [
        {
            itemNested: [
                {
                    itemNested2: [{
                        id: "2"
                    }
                    ]
                }
            ]
        }
    ]
};

function findById(obj, id) {
    var result;
    for (var p in obj) {
        if (obj.id === id) {
            return obj;
        } else {
            if (typeof obj[p] === 'object') {
                result = findById(obj[p], id);
                if (result) {
                    return result;
                }
            }
        }
    }
    return result;
}


var result = findById(data, "2");
console.log(result);
</script>

Answer 1

From a once over:

• Be careful for js structure with cycles (like nodes in the DOM), you will get into an infinite loop.
• This will also not find dupes, that may or may not be a problem
• You also want to think about whether you want to prevent finding id in the inherited values with o.hasOwnProperty(p)
• Dont check for if (obj.id === id) { in your loop, it's a waste of cycles. Check prior
• Personally I tend to go either for the Spartan o or the full object, obj seems meh

I would use this version:

function findById(o, id) {
    //Early return
    if( o.id === id ){
      return o;
    }
    var result, p; 
    for (p in o) {
        if( o.hasOwnProperty(p) && typeof o[p] === 'object' ) {
            result = findById(o[p], id);
            if(result){
                return result;
            }
        }
    }
    return result;
}

Answer 2

The way your data is structured prevents it. Currently what you're doing has the complexity of \$O(n)\$ which means that in the worst case (is isn't found) you'll iterate over all the elements.

There are faster way to search but they all rely (as far as I know) on an ordered object (Array / Tree / ...).

If you could get your data in an ordered balanced binary tree than searching it would take \$O(log_2(n))\$ which will be extremely faster.

If you had an ordered list of all the ids in an object than you could do a binary search on it and again find that element in \$O(log_2(n))\$

Answer 3

You could extend Konjin version searching by any object property, and optionaly return object property instead of object :

function findByProp(o, prop, val, retprop) {
    if(o==null) return false;
    if( o[prop] === val ){
        return (retprop) ? o[retprop] : o;
    }
    var result, p; 
    for (p in o) {
       if( o.hasOwnProperty(p) && typeof o[p] === 'object' ) {
           result = findByProp(o[p], prop, val);
           if(result){
               return (retprop) ? result[retprop] : result;
           }
       }
    }
    return (retprop) ? result[retprop] : result;
}

Function parameter are o : object of recursive search, prop/val : searched prop/val, and retprop (optional) : property name to return value instead of object.

First line " if(o==null) return false; " has been added in order to trap any null value for a property during iteration that may cause an error.