DOM Tree Traversal through Breadth-first Search (BFS)

Please follow & like us :)

First We will learn about What is BFS?

Breadth-first search (BFS) is an algorithm for traversing tree structures. The algorithm starts at the root node and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

BFS Animation Description

In Web Developer Technical Interview, you will be asked to parse DOM elements and how you can improve performance. You should use BFS or DFS algorithm to solve the question.

Take a look DOM tree example below:

<div class="main">
  <div class="list1">
    <ul class="ul1">
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
    </ul>
    <ul class="ul2">
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
    </ul>
    <ul class="ul3">
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
      <li><a href="#"><img src=""/></a></li>
    </ul>
  </div>
  <div class="list2"><span><p></p></span></div>
</div>

We have given list elements in this example and asked to get image node from each list element. We can use BFS algorithm to implement this task.

const bfs = (node) => {  
  let arr = [];  
  if (node) {  
    let queue = [];  
    queue.unshift(node);  
    while (queue.length != 0) {  
      let currentN = queue.shift();  
      arr.push(currentN);  
      let childN = currentN.children;  
      for (let i = 0; i < childN.length; i++)  
        queue.push(childN[i]);  
      }  
    }  
    return arr;  
}

let root = document.querySelector('.main');
bfs(root);