How to find a node in a tree with JavaScript

Question

I have and object literal that is essentially a tree that does not have a fixed number of levels. How can I go about searching the tree for a particualy node and then return that node when found in an effcient manner in javascript?

Essentially I have a tree like this and would like to find the node with the title 'randomNode_1'

var data = [
{
title: 'topNode',
 children: [
   {
       title: 'node1',
       children: [
       {
           title: 'randomNode_1'
       },
       {   
           title: 'node2',
           children: [
           {
               title: 'randomNode_2',
               children:[
               {   
                   title: 'node2',
                   children: [
                   {
                       title: 'randomNode_3',
                   }]
               }
               ]
           }]
       }]
   }
  ]
 }];

Answer 1

Basing this answer off of @Ravindra's answer, but with true recursion.

function searchTree(element, matchingTitle){
     if(element.title == matchingTitle){
          return element;
     }else if (element.children != null){
          var i;
          var result = null;
          for(i=0; result == null && i < element.children.length; i++){
               result = searchTree(element.children[i], matchingTitle);
          }
          return result;
     }
     return null;
}

Then you could call it:

var element = data[0];
var result = searchTree(element, 'randomNode_1');

Answer 2

Here's an iterative solution:

var stack = [], node, ii;
stack.push(root);

while (stack.length > 0) {
    node = stack.pop();
    if (node.title == 'randomNode_1') {
        // Found it!
        return node;
    } else if (node.children && node.children.length) {
        for (ii = 0; ii < node.children.length; ii += 1) {
            stack.push(node.children[ii]);
        }
    }
}

// Didn't find it. Return null.
return null;

Answer 3

Here's an iterative function using the Stack approach, inspired by FishBasketGordo's answer but taking advantage of some ES2015 syntax to shorten things.

Since this question has already been viewed a lot of times, I've decided to update my answer to also provide a function with arguments that makes it more flexible:

function search (tree, value, key = 'id', reverse = false) {
  const stack = [ tree[0] ]
  while (stack.length) {
    const node = stack[reverse ? 'pop' : 'shift']()
    if (node[key] === value) return node
    node.children && stack.push(...node.children)
  }
  return null
}

This way, it's now possible to pass the data tree itself, the desired value to search and also the property key which can have the desired value:

search(data, 'randomNode_2', 'title')

Finally, my original answer used Array.pop which lead to matching the last item in case of multiple matches. In fact, something that could be really confusing. Inspired by Superole comment, I've made it use Array.shift now, so the first in first out behavior is the default.

If you really want the old last in first out behavior, I've provided an additional arg reverse:

search(data, 'randomNode_2', 'title', true)

Answer 4

My answer is inspired from FishBasketGordo's iterativ answer. It's a little bit more complex but also much more flexible and you can have more than just one root node.

/**searchs through all arrays of the tree if the for a value from a property
 * @param aTree : the tree array
 * @param fCompair : This function will receive each node. It's upon you to define which 
                     condition is necessary for the match. It must return true if the condition is matched. Example:
                        function(oNode){ if(oNode["Name"] === "AA") return true; }
 * @param bGreedy? : us true to do not stop after the first match, default is false
 * @return an array with references to the nodes for which fCompair was true; In case no node was found an empty array
 *         will be returned
*/
var _searchTree = function(aTree, fCompair, bGreedy){
    var aInnerTree = []; // will contain the inner children
    var oNode; // always the current node
    var aReturnNodes = []; // the nodes array which will returned

    // 1. loop through all root nodes so we don't touch the tree structure
    for(keysTree in aTree) {
        aInnerTree.push(aTree[keysTree]);
    }
    while(aInnerTree.length > 0) {
        oNode = aInnerTree.pop();
        // check current node
        if( fCompair(oNode) ){
            aReturnNodes.push(oNode);
            if(!bGreedy){
                return aReturnNodes;
            }
        } else { // if (node.children && node.children.length) {
            // find other objects, 1. check all properties of the node if they are arrays
            for(keysNode in oNode){
                // true if the property is an array
                if(oNode[keysNode] instanceof Array){
                    // 2. push all array object to aInnerTree to search in those later
                    for (var i = 0; i < oNode[keysNode].length; i++) {
                        aInnerTree.push(oNode[keysNode][i]);
                    }
                }
            }
        }
    }
    return aReturnNodes; // someone was greedy
}

Finally you can use the function like this:

var foundNodes = _searchTree(data, function(oNode){ if(oNode["title"] === "randomNode_3") return true; }, false);
console.log("Node with title found: ");
console.log(foundNodes[0]);

And if you want to find all nodes with this title you can simply switch the bGreedy parameter:

var foundNodes = _searchTree(data, function(oNode){ if(oNode["title"] === "randomNode_3") return true; }, true);
console.log("NodeS with title found: ");
console.log(foundNodes);