How to do a recursive search of this Javascript/JSON tree?

Question

I'm writing some Javascript code. I have a JSON object that looks like this (spacing modified for readability):

var myNodes = [
    {
        id: 4, 
        children: [
            {
                id: 1, 
                children: [
                ]
            },
            {
                id: 3, 
                children: [
                ]
            }
        ]
    },
    {
        id: 2, 
        children: [
        ]
    },
    {
        id: 6, 
        children: [
            {
                id: 5, 
                children: [
                ]
            }
        ]
    }
]

Each node's id in this data structure is unique. However, other than that, there is no fixed or known relationship amongst the ID numbers at all. And there is no limit to the number of children at each level.

If I want search this tree and return the node with id == 6. How can I do it? I have written the following code, however after it encounters the first leaf node the entire algorithm returns false, which is clearly not right. I'm just trying to do a basic depth-first-search. But I don't want to add extra fields to this data and "mark" the nodes as I have seen in some DFS implementations on the web.

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++)
    {
        console.log("Comparing treeNodes element with ID==" + treeNodes[nodeIdx].id + " to SearchID==" + searchID);
        if (treeNodes[nodeIdx].id == searchID)
        {    
            console.log("Match!");
            return treeNodes[nodeIdx];
        }
        else
        {
            console.log("No Match! Trying " + treeNodes[nodeIdx].children.length + " Children of Node ID#" + treeNodes[nodeIdx].id);
            return this.nodeSearch(treeNodes[nodeIdx].children, searchID); 
        }
    }
    console.log("Done trying " + treeNodes.length + " children. Returning False");
    return false;
};

Answer 1

There's a problem with your algorithm. Both your if and your else return unconditionally, which means that a return will inevitably occur on the first iteration through each loop, and the algorithm will only check the first of each of its descendants (in this case just nodes 4 and 1 and nothing else). You need to check whether the recursive call returned a found value, and only pass that up the recursive tree if so. I think this should provide you a fixed solution:

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++) {
        var currentNode = treeNodes[nodeIdx],
            currentId = currentNode.id,
            currentChildren = currentNode.children;
        console.log("Comparing treeNodes element with ID==" + 
                    currentId + " to SearchID==" + searchID);
        if (currentId == searchID) {    
            console.log("Match!");
            return currentNode;
        }
        else {
            console.log("No Match! Trying " + currentChildren.length + 
                        " Children of Node ID#" + currentId);
            var foundDescendant = this.nodeSearch(currentChildren, searchID); 
            if (foundDescendant) {
                return foundDescendant;
            }
        }
    }
    console.log("Done trying " + treeNodes.length + " children. Returning False");
    return false;
};

I've also added some variables to help make the code a bit DRYer and help prevent some of the bugs mentioned earlier.

Answer 2

I've chosen to use a json-easy-filter instead of writing a custom solution for a similar task.

Answer 3

You can use DefiantJS (https://github.com/hbi99/defiant.js). Using this js-lib, you can search JSON structures with XPath queries. And it is as easy as exemplified with code below. Here is the same code at JSFiddle: http://jsfiddle.net/hbi99/a55au8h5/

PS: I added the "name" property for this sample code.

var myNodes = [
    {
        "id": 4,
        "name": 'name_of_4',
        "children": [
            {
                "id": 1,
                "name": 'name_of_1',
                "children": []
            },
            {
                "id": 3,
                "name": 'name_of_3',
                "children": []
            }
        ]
    },
    {
        "id": 2,
        "name": 'name_of_2',
        "children": []
    },
    {
        "id": 6,
        "name": 'name_of_6',
        "children": [
            {
                "id": 5,
                "name": 'name_of_5',
                "children": []
            }
        ]
    }
],
found = JSON.search(myNodes, '//*[id=6]');

console.log( found[0].name ); // name_of_6