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.

Answer 1

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 appended¹ (shallow copy) to the queue.

_{¹ 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;
}