Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find an element in an array recursively

I have an array of objects. Every object in the array has an id and an item property that is an array containing other object. I need to be able to find an element in an array by id. Here is a sample of what I have done so far, but the recursive function is always returning undefined.

How can I quit the function and return the item when I have called the function recursively several times?

   $(function () {
    var treeDataSource = [{
        id: 1,
        Name: "Test1",
        items: [{
            id: 2,
            Name: "Test2",
            items: [{
                id: 3,
                Name: "Test3"
            }]
        }]
    }];
    var getSubMenuItem = function (subMenuItems, id) {
        if (subMenuItems && subMenuItems.length > 0) {
            for (var i = 0; i < subMenuItems.length; i++) {
                var item;
                if (subMenuItems[i].Id == id) {
                    item = subMenuItems[i];
                    return item;
                };
                getSubMenuItem(subMenuItems[i].items, id);
            };
        };
    };
    var searchedItem = getSubMenuItem(treeDataSource, 3);
    alert(searchedItem.id);
});

jsFiddle

like image 355
Mdb Avatar asked Jan 28 '13 09:01

Mdb


People also ask

Can we write recursive function to search element in an array?

This C Program uses recursive function & searches for an element in an unsorted list and display it's position of occurrence.

Which Searching can be performed recursively?

Binary search is an inherently recursive algorithm: we can implement iteratively, but it makes more sense algorithmicly to do it recursively (though for certain implementations you might choose to do it iteratively for efficiency reasons). Binary search works by splitting up a sorted data set into two parts.

Can linear search be performed recursively?

Both can be used Was this answer helpful?


2 Answers

You should replace

  getSubMenuItem(subMenuItems[i].items, id);

with

  var found = getSubMenuItem(subMenuItems[i].items, id);
  if (found) return found;

in order to return the element when it is found.

And be careful with the name of the properties, javascript is case sensitive, so you must also replace

  if (subMenuItems[i].Id == id) {

with

  if (subMenuItems[i].id == id) {

Demonstration


Final (cleaned) code :

var getSubMenuItem = function (subMenuItems, id) {
    if (subMenuItems) {
        for (var i = 0; i < subMenuItems.length; i++) {
            if (subMenuItems[i].id == id) {
                return subMenuItems[i];
            }
            var found = getSubMenuItem(subMenuItems[i].items, id);
            if (found) return found;
        }
    }
};
like image 168
Denys Séguret Avatar answered Oct 16 '22 09:10

Denys Séguret


I know its late but here is a more generic approach

Array.prototype.findRecursive = function(predicate, childrenPropertyName){
    if(!childrenPropertyName){
        throw "findRecursive requires parameter `childrenPropertyName`";
    }
    let array = [];
    array = this;
    let initialFind =  array.find(predicate);
    let elementsWithChildren  = array.filter(x=>x[childrenPropertyName]);
    if(initialFind){
        return initialFind;
    }else if(elementsWithChildren.length){
        let childElements = [];
        elementsWithChildren.forEach(x=>{
            childElements.push(...x[childrenPropertyName]);
        });
        return childElements.findRecursive(predicate, childrenPropertyName);
    }else{
        return undefined;
    }
}

to use it:

var array = [<lets say an array of students who has their own students>];
var joe = array.findRecursive(x=>x.Name=="Joe", "students");

and if you want filter instead of find

Array.prototype.filterRecursive = function(predicate, childProperty){
    let filterResults = [];
    let filterAndPushResults = (arrayToFilter)=>{
        let elementsWithChildren  = arrayToFilter.filter(x=>x[childProperty]);
        let filtered = arrayToFilter.filter(predicate);
        filterResults.push(...filtered);
        if(elementsWithChildren.length){
            let childElements = [];
            elementsWithChildren.forEach(x=>{
                childElements.push(...x[childProperty]);
            });
            filterAndPushResults(childElements);
        }
    };
    filterAndPushResults(this);
    return filterResults;
}
like image 4
anaval Avatar answered Oct 16 '22 10:10

anaval