Locating element in a nested tree - JavaScript

Question

Needed help in writing a function to search an element in the sample tree.

var sampletree = [
  "a",
  "b",
  "c",
  [
    "d",
    "e",
    [
      "f",
      "h",
      "i",
      [
        "z",
        "x"
      ]
    ]
  ],
  [
    "y",
    "q",
    "t",
    [
      "m",
      "n",
      [
        "o",
        "p"
      ],
      [
        "r",
        "s",
        [
          "u",
          "v"
        ]
      ]
    ]
  ],
  "g"
]

Wanted to return true/false by searching for inner elements such as o,p,u,v in the tree using Breadth First Search by javascript only and no frameworks / libraries.

I used a for loop to run through and then .indexOf but was not able to obtain it.


Show source
| javascript   | dom   | search   | tree   | breadth-first-search   2016-12-17 00:12 1 Answers

Answers ( 1 )

  1. 2016-12-17 00:12

    You could use this function:

    function findNodeBFS(tree, node) {
        var queue = tree.slice();
        for (var i = 0; i < queue.length; i++) {
            if (queue[i] === node) return true;
            if (Array.isArray(queue[i])) queue = queue.concat(queue[i]);
        }
        return false;
    }
    
    var sampletree = [ "a", "b", "c", [ "d", "e", [ "f", "h", "i", [ "z", "x" ] ] ], [ "y", "q", "t", [ "m", "n", [ "o", "p" ], [ "r", "s", [ "u", "v" ] ] ] ], "g" ];
    
    console.log(findNodeBFS(sampletree, "u")); // true
    console.log(findNodeBFS(sampletree, "j")); // false

    Explanation

    This algorithm maintains a queue, which you can see as a kind of "to do" list. It starts as a copy of the tree. The code iterates over the nodes, but only those at the top-level. Whenever it encounters an array -- which represents a deeper level -- those children are added to the end of the queue, meaning: "I will deal with you later".

    This is what happens in this line of code:

    if (Array.isArray(queue[i])) queue = queue.concat(queue[i]);
    

    So if queue[i] is an array, its elements are appended1 (shallow copy) to the queue.

    1 In fact, concat does not mutate the given array, but produces a new one, which is the concatenation of queue and queue[i]. By assigning that new array back to queue, we get the effect of appending. Instead of this we could have done [].push.apply(queue, queue[i]), which mutates the first, by appending the second, in-place. But it may look a bit more cryptic.

    Note that we do not append the array we found, but each element in it. So when the loop arrives at that appended data, it will in fact visit a deeper level of the original tree. This is indeed what BFS means: first visit the nodes on the level you are currently on, and only treat deeper levels after you have finished the current level. A queue (first in, first out) is the ideal data structure for doing just that.

    Depth First Search Variant

    The DFS variant would be this recursive ES6 function:

    function findNodeDFS(tree, node) {
        return Array.isArray(tree) && tree.some( val => findNode(val, node) ) 
               || node === tree;
    }
    
◀ Go back