JavaScript recursive search in JSON object

Question

I am trying to return a specific node in a JSON object structure which looks like this

{
    "id":"0",
    "children":[
        {
            "id":"1",
            "children":[...]
        },
        {
            "id":"2",
            "children":[...]
        }
    ]
}

So it's a tree-like child-parent relation. Every node has a unique ID. I'm trying to find a specific node like this

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        currentNode.children.forEach(function (currentChild) {            
            findNode(id, currentChild);
        });
    }
}

I execute the search for example by findNode("10", rootNode). But even though the search finds a match the function always returns undefined. I have a bad feeling that the recursive function doesn't stop after finding the match and continues running an finally returns undefined because in the latter recursive executions it doesn't reach a return point, but I'm not sure how to fix this.

Please help!

since it is answer, I just want to point out that foreach loop can't stop in javascript. do not use foreach in algorithm. — wayne
– wayne, Commented Mar 6, 2014 at 11:21
Why are you performing a search on a JSON object in the first place? You should maybe consider doing the search in the place where the JSON object was generated, hopefully the database. — user3180309
– user3180309, Commented Mar 5, 2018 at 14:54
@jmb.mage because in the real world you often have to solve tasks which don't have ideal circumstances and whose details are out of your reach. This is one of them. — Dropout
– Dropout, Commented Mar 5, 2018 at 15:41
@milahu deepdash started getting developed 4 years after the question was posted and this functionality definitely doesn't need a library to be slapped on top of it to achieve the requested results.. — Dropout
– Dropout, Commented Oct 31, 2022 at 11:59

Butt4cak3 · Accepted Answer · 2014-03-06 11:17:43Z

63

When searching recursively, you have to pass the result back by returning it. You're not returning the result of findNode(id, currentChild), though.

function findNode(id, currentNode) {
    var i,
        currentChild,
        result;

    if (id == currentNode.id) {
        return currentNode;
    } else {

        // Use a for loop instead of forEach to avoid nested functions
        // Otherwise "return" will not work properly
        for (i = 0; i < currentNode.children.length; i += 1) {
            currentChild = currentNode.children[i];

            // Search in the current child
            result = findNode(id, currentChild);

            // Return the result if the node has been found
            if (result !== false) {
                return result;
            }
        }

        // The node has not been found and we have no more options
        return false;
    }
}

answered Mar 6, 2014 at 11:17

Butt4cak3

2,43917 silver badges15 bronze badges

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

5 Comments

Denis Weerasiri Over a year ago

I had to add an additional check to the for loop (i.e., for (i = 0; currentNode.children !== undefined && i < currentNode.children.length; i += 1)) to avoid the error "TypeError: Cannot read property 'length' of undefined" at leaf nodes where "children" do not exist.

amitava mozumder Over a year ago

breaks with can't find length of undefined. it's a document object.

Guntram Over a year ago

I am searching like that for a child by name in all bins in premierepro extendscript now :)

jakxnz Over a year ago

Here's a similar solution, but with less code stackoverflow.com/a/52205610/3666971

Stefan Steiger Over a year ago

You should probably return null instead of false, if you return an object of type T at the other place. But JavaScript's dynamic types are very forgiving.

Triode · Accepted Answer · 2019-06-06 09:55:27Z

5

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        var result;
        currentNode.children.forEach(function(node){
            if(node.id == id){
                result = node;
                return;
            }
        });
        return (result ? result : "No Node Found");
    }
}
console.log(findNode("10", node));

This method will return the node if it present in the node list. But this will loop through all the child of a node since we can't successfully break the forEach flow. A better implementation would look like below.

function findNode(id, currentNode) {

    if (id == currentNode.id) {
        return currentNode;
    } else {
        for(var index in currentNode.children){
            var node = currentNode.children[index];
            if(node.id == id)
                return node;
            findNode(id, node);
        }
        return "No Node Present";
    }
}
console.log(findNode("1", node));

edited Jun 6, 2019 at 9:55

answered Mar 6, 2014 at 11:20

Triode

11.4k2 gold badges40 silver badges48 bronze badges

2 Comments

user8106148 Over a year ago

Dear @Triode, You define result but never use it.

Triode Over a year ago

@Mehr88sh Sorry, Rectified!!

Peter · Accepted Answer · 2018-07-04 07:49:46Z

4

I use the following

var searchObject = function (object, matchCallback, currentPath, result, searched) {
    currentPath = currentPath || '';
    result = result || [];
    searched = searched || [];
    if (searched.indexOf(object) !== -1 && object === Object(object)) {
        return;
    }
    searched.push(object);
    if (matchCallback(object)) {
        result.push({path: currentPath, value: object});
    }
    try {
        if (object === Object(object)) {
            for (var property in object) {
                if (property.indexOf("$") !== 0) {
                    //if (Object.prototype.hasOwnProperty.call(object, property)) {
                        searchObject(object[property], matchCallback, currentPath + "." + property, result, searched);
                    //}
                }
            }
        }
    }
    catch (e) {
        console.log(object);
        throw e;
    }
    return result;
}

Then you can write

searchObject(rootNode, function (value) { return value != null && value != undefined && value.id == '10'; });

Now this works on circular references and you can match on any field or combination of fields you like by changing the matchCallback function.

edited Jul 4, 2018 at 7:49

answered Aug 24, 2017 at 7:48

Peter

38.9k39 gold badges151 silver badges213 bronze badges

3 Comments

frumbert Over a year ago

the match callback is a great idea and I also like that you get the path as well as the object. Cheers!

atfede Over a year ago

It works, thank you. You should mention that in order to search for a specific node you should change this part: if (property.indexOf("NameOfTheNodeYouAreLookingFor") !== 0) {} And also to change to return object; instead of return result;

Peter Over a year ago

@atfede the reason i return result is to allow for more then one hit. I'm a bit unsure what you mean with if (property.indexOf("NameOfTheNodeYouAreLookingFor") !== 0) {}

Scott Sauyet · Accepted Answer · 2021-01-05 03:56:11Z

Since this old question has been brought back up, here's a different approach. We can write a fairly generic searchTree function which we then use in a findId function. searchTree does the work of traversing the object; it accepts a callback as well as the tree; the callback determines if a node matches. As well as the node, the callback is supplied two functions, next and found, which we call with no parameters to signal, respectively, that we should proceed or that we've found our match. If no match is found, we return null.

It looks like this:

const searchTree = (fn) => (obj) =>
  Array.isArray(obj)
    ? obj.length == 0
      ? null
      : searchTree (fn) (obj [0]) || searchTree (fn) (obj .slice (1))
    : fn (
      obj,
      () => searchTree (fn) (obj .children || []),
      () => obj
    )

const findId = (target, obj) => searchTree (
  (node, next, found) => node.id == target ? found () : next(),
) (tree)


const tree = {id: 1, name: 'foo', children: [
  {id: 2, name: 'bar', children: []}, 
  {id: 3, name: 'baz', children: [
    {id: 17, name: 'qux', children: []}, 
    {id: 42, name: 'corge', children: []},
    {id: 99, name: 'grault', children: []}
  ]}
]}


console .log (findId (42, tree))
console .log (findId (57, tree))

This code is specific to the structure where subnodes are found in an array under the property children. While we can make this more generic as necessary, I find this a common structure to support.

There is a good argument that this would be better written with mutual recursion. If we wanted, we could get the same API with this version:

const searchArray = (fn) => ([x, ...xs]) =>
  x === undefined
    ? null
    : searchTree (fn) (x) || searchArray (fn) (xs)

const searchTree = (fn) => (obj) =>
  fn (
    obj,
    () => searchArray (fn) (obj .children || []),
    (x) => x
  )

This works the same way. But I find the code cleaner. Either should do the job, though.

vincent · Accepted Answer · 2021-01-14 01:03:30Z

3

We use object-scan for our data processing needs. It's conceptually very simple, but allows for a lot of cool stuff. Here is how you could solve your question

// const objectScan = require('object-scan');

const findNode = (id, input) => objectScan(['**'], {
  abort: true,
  rtn: 'value',
  filterFn: ({ value }) => value.id === id
})(input);

const data = { id: '0', children: [{ id: '1', children: [ { id: '3', children: [] }, { id: '4', children: [] } ] }, { id: '2', children: [ { id: '5', children: [] }, { id: '6', children: [] } ] }] };

console.log(findNode('6', data));
// => { id: '6', children: [] }

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

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

edited Jan 14, 2021 at 1:03

answered Oct 7, 2019 at 4:06

vincent

2,1893 gold badges19 silver badges30 bronze badges

3 Comments

Scott Sauyet Over a year ago

Several other answers here mention that they work on circular objects. Does object-scan take this into account?

vincent Over a year ago

Yes. However since it's a performance tradeoff you need to handle it explicitly. Ie you could simply add breakFn: ({ isCircular }) => isCircular

Scott Sauyet Over a year ago

I do love how simple object-scan makes this problem. I'm not yet convinced that I want to try it in my own code, I may get there soon though.

697 · Accepted Answer · 2023-02-13 20:26:52Z

3

Similar questions were answered several times, but I just want to add a universal method that includes nested arrays

const cars = [{
  id: 1,
  name: 'toyota',
  subs: [{
    id: 43,
    name: 'supra'
  }, {
    id: 44,
    name: 'prius'
  }]
}, {
  id: 2,
  name: 'Jeep',
  subs: [{
    id: 30,
    name: 'wranger'
  }, {
    id: 31,
    name: 'sahara'
  }]
}]

function searchObjectArray(arr, key, value) {
  let result = [];
  
  arr.forEach((obj) => {
    if (obj[key] === value) {
      result.push(obj);
    } else if (obj.subs) {
      result = result.concat(searchObjectArray(obj.subs, key, value));
    }
  });
  console.log(result)
  return result;
}

searchObjectArray(cars, 'id', '31') 

searchObjectArray(cars, 'name', 'Jeep')

I hope this helps someone

edited Feb 13, 2023 at 20:26

answered Feb 13, 2023 at 20:16

697

6518 silver badges22 bronze badges

Comments

xakepp35 · Accepted Answer · 2019-02-09 19:10:56Z

0

I really liked a tree search! A tree is an extremely common data structure for most of today's complex structured tasks. So I just had similar task for lunch too. I even did some deep research, but havent actually found anything new! So what I've got for you today, is "How I implemented that in modern JS syntax":

// helper
find_subid = (id, childArray) => {
    for( child of childArray ) {
        foundChild = find_id( i, child ); // not sub_id, but do a check (root/full search)!
        if( foundChild ) // 200 
            return foundChild;
    }
    return null; // 404
}

// actual search method
find_id = (id, parent) => (id == parent.id) : parent : find_subid(id, parent.childArray);

answered Feb 9, 2019 at 19:10

xakepp35

3,3328 gold badges36 silver badges63 bronze badges

Comments

Roman86 · Accepted Answer · 2020-05-20 15:25:23Z

Recursive structure search, modification, keys/values adjustments/replacement.

Usage Example:

const results = []; // to store the search results

mapNodesRecursively(obj, ({ v, key, obj, isCircular }) => {
    // do something cool with "v" (or key, or obj)
    // return nothing (undefined) to keep the original value

    // if we search:
    if (key === 'name' && v === 'Roman'){
        results.push(obj);
    }

    // more example flow:
    if (isCircular) {
        delete obj[key]; // optionally - we decide to remove circular links
    } else if (v === 'Russia') {
        return 'RU';
    } else if (key.toLocaleLowerCase() === 'foo') {
        return 'BAR';
    } else if (key === 'bad_key') {
        delete obj[key];
        obj['good_key'] = v;
    } else {
        return v; // or undefined, same effect
    }
});

Tips and hints:

You can use it as a search callback, just return nothing (won't affect anything) and pick values you need to your Array/Set/Map.

Notice that callback is being run on every leaf/value/key (not just objects).

Or you can use the callback to adjust particular values and even change keys. Also it automatically detects circular loops and provides a flag for you to decide how to handle them.

The code

(uses ES6)

Function itself + some example demo data

function mapNodesRecursively(obj, mapCallback, { wereSet } = {}) {
    if (!wereSet) {
        wereSet = new Set();
    }

    if (obj && (obj === Object(obj) || Array.isArray(obj))) {
        wereSet.add(obj);

        for (let key in obj) {
            if (!obj.hasOwnProperty(key)){
                continue;
            }

            let v = obj[key];

            const isCircular = wereSet.has(v);

            const mapped = mapCallback({ v, key, obj, isCircular });
            if (typeof (mapped) !== 'undefined') {
                obj[key] = mapped;
                v = mapped;
            }

            if (!isCircular) {
                mapNodesRecursively(v, mapCallback, { wereSet });
            }
        }
    }

    return obj;
}

let obj = {
    team: [
        {
            name: 'Roman',
            country: 'Russia',
            bad_key: 123,
        },
        {
            name: 'Igor',
            country: 'Ukraine',
            FOO: 'what?',
        },
        {
            someBool: true,
            country: 'Russia',
        },
        123,
        [
            1,
            {
                country: 'Russia',
                just: 'a nested thing',
                a: [{
                    bad_key: [{
                        country: 'Russia',
                        foo: false,
                    }],
                }],
            },
        ],
    ],
};

// output the initial data
document.getElementById('jsInput').innerHTML = JSON.stringify(obj, null, 2);

// adding some circular link (to fix with our callback)
obj.team[1].loop = obj;

mapNodesRecursively(obj, ({ v, key, obj, isCircular }) => {
    if (isCircular) {
        delete obj[key]; // optionally - we decide to remove circular links
    } else if (v === 'Russia') {
        return 'RU';
    } else if (key.toLocaleLowerCase() === 'foo') {
        return 'BAR';
    } else if (key === 'bad_key') {
        delete obj[key];
        obj['good_key'] = v;
    } else {
        return v;
    }
});

// output the result - processed object
document.getElementById('jsOutput').innerHTML = JSON.stringify(obj, null, 2);

.col {
  display: inline-block;
  width: 40%;
}

<div>
  <h3>Recursive structure modification, keys/values adjustments/replacement</h3>
  <ol>
    <li>
      Replacing "Russia" values with "RU"
    </li>
    <li>
      Setting the value "BAR" for keys "FOO"
    </li>
    <li>
      Changing the key "bad_key" to "good_key"
    </li>
  </ol>
  <div class="col">
    <h4>BEFORE</h4>
    <pre id="jsInput"></pre>
  </div>
  <div class="col">
    <h4>AFTER</h4>
    <pre id="jsOutput"></pre>
  </div>
</div>

Collectives™ on Stack Overflow

JavaScript recursive search in JSON object

8 Answers 8

5 Comments

2 Comments

3 Comments

Comments

3 Comments

Comments

Comments

Usage Example:

Tips and hints:

The code

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

5 Comments

2 Comments

3 Comments

Comments

3 Comments

Comments

Comments

Usage Example:

Tips and hints:

The code

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related