Recursively searching a nested array in JS

Question

I'm trying to search a nested json array for a single object with a matching name. My data structure looks like this:

[
    {
        "type": "directory",
        "name": "/home/user/test-tree",
        "contents": [
            {
                "type": "directory",
                "name": "my-folder",
                "contents": [
                    {
                        "type": "directory",
                        "name": "nested-folder",
                        "contents": []
                    }
                ]
            },
            {
                "type": "directory",
                "name": "node_modules",
                "contents": [
                    {
                        "type": "directory",
                        "name": "gunzip-file",
                        "contents": []
                    }
                ]
            }
        ]
    }
]

So in this example, I could be searching for a directory called "node_modules" and it should return that entire object, including its contents. This is just a sample, my actual dataset could be pretty big - the tree could represent all directories on a filesystem for example.

This is the code that I'm using right now - it seems to work for this example but it doesn't seem to work properly with larger datasets, and I can't really see what's wrong with it so if someone can spot anything I'd appreciate it.

    function treeSearch(array, dirName) {
        for (let i = 0; i < array.length; i++) {
            if (array[i].name === dirName) {
                return array[i]
            }
            else if (array[i].contents) {
                if (array[i].contents.length > 0) {
                    return treeSearch(array[i].contents, dirName)
                }
            }
        }
    }

is that mean that there is just one contents and that content have object or many contents have many objects — HamzaNig
– HamzaNig, Commented Jan 11, 2019 at 11:52
@HamzaNig It represents a directory structure so the contents will be the children of that directory. For example, if I have a directory called test and there are two more empty directories under it, the test object will have a contents array with two objects and those two objects will each have their own empty contents arrays because they have no children. Does that make sense? — Sean Morris
– Sean Morris, Commented Jan 11, 2019 at 11:55

Nina Scholz · Accepted Answer · 2019-01-11 12:05:10Z

4

You could take a recursive function which iterates the array with a possibility for a short circiut, if the value is found.

function find(array, value) {
    var result;
    array.some(o => result = o.name === value && o || find(o.contents, value));
    return result || undefined;
}

var data = [{ type: "directory", name: "/home/user/test-tree", contents: [{ type: "directory", name: "my-folder", contents: [{ type: "directory", name: "nested-folder", contents: [] }] }, { type: "directory", name: "node_modules", contents: [{ type: "directory", name: "gunzip-file", contents: [] }] }] }]

console.log(find(data, "node_modules"));

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jan 11, 2019 at 12:05

answered Jan 11, 2019 at 11:54

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Karim · Accepted Answer · 2019-02-04 12:00:50Z

There's an error in your code, at the moment you're just recursing on a single branch of the three, you're not recursing across the whole data structure, infact if you're trying to search for "node_modules" your code returns undefined.

Try to apply this tiny modification to your code

const data = [
    {
        "type": "directory",
        "name": "/home/user/test-tree",
        "contents": [
            {
                "type": "directory",
                "name": "my-folder",
                "contents": [
                    {
                        "type": "directory",
                        "name": "nested-folder",
                        "contents": []
                    }
                ]
            },
            {
                "type": "directory",
                "name": "node_modules",
                "contents": [
                    {
                        "type": "directory",
                        "name": "gunzip-file",
                        "contents": []
                    }
                ]
            }
        ]
    }
];

function treeSearch(array, dirName) {
  for (let i = 0; i < array.length; i++) {
     if (array[i].name === dirName) {
       return array[i];
     }
     else if (array[i].contents && array[i].contents.length) {
       const result = treeSearch(array[i].contents, dirName);
       // return the result only if it's actually found otherwise keep looping
       if(result) return result;
     }
   }
}

console.log(treeSearch(data, "node_modules"));

That's done it. Thanks! Such a simple omission can't believe I missed it!

Collectives™ on Stack Overflow

Recursively searching a nested array in JS

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related