DOM Tree Traversal through Depth-first Search (DFS)

First We will learn about What is DFS?

Depth–first search (DFS) is an algorithm for traversing tree structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

DFS Animated Description

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 of each list element. We can use DFS algorithm to implement this task.

const parseDom = (node, arr) => {

  if (node.tagName.toLowerCase() == 'img') {
    arr.push(node);
  }

  let chNodes = node.children;

  for (let i = 0; i < chNodes.length; i++) {
    parseDom(chNodes[i], arr);
  }
  
  return arr;

}

const divId = document.querySelector('.list1');
let arr = [];

const imgArr = parseDom(divId, arr);
console.log(imgArr);

Here is the snapshot for recursive method for DFS:

const dfs = (root, arr) => {
  if (root) {
    arr.push(root);
  }
  let childNodes = root.children;
  for (let i = 0; i < chNodes.length; i++) {
    dfs(chNodes[i], arr);
  }
  return arr;
}

To Improve performance, instead of recursive method we can use stack data structure which allows last in first out approach.

const dfsTree = (node, arr) => {
   
  let stk = [];
  stk.push(node);
  while(stk.length !== 0){
    let currentNode = stk.pop();
    arr.push(currentNode);
    if(currentNode && currentNode.children && currentNode.children.length >0){
      for(let i = currentNode.children.length - 1; i>=0; i--){
        stk.push(currentNode.children[i]);
      }
    }
  }
  return arr;
}
const divId = document.querySelector('.list1');
let arr = [];

const imgArr = dfsTree(divId, arr);
console.log(imgArr);