DEV Community 👩‍💻👨‍💻

Greg
Greg

Posted on

Traverse The DOM With Depth First Search Recursion

STOP READING THIS IF YOU CAN USE THE getElementById or querySelector API

Repo

TLDR;

myQuerySelectorAll(['div', 'p']);

Enter fullscreen mode Exit fullscreen mode

Intro

The first time in the wild I came across a practical need to use an interview coding algo, I know what you are thinking whoaa no way.

Normally the getElementById API is great for targeting specific dom nodes. In my case I needed to target and style deeply nested p tags in the DOM tree that were served from a back end headless Content Management System (Think umbraco, strapi, shopify). There was no attributes so I was left with tagNames... and to the rescue came Depth First Search (DFS).

With the DFS approach recursion was inevitable to untangle the deeply nested if/else statements I created. The next question is in what order since there are 3 orders:

  • 1 pre-order
  • 2 in-order
  • 3 post-order

Without getting into the weeds we are going with preorder here is a simple schematic of how the orders work.

Image description

Essentially I want to traverse from center to the left back up to center and to the right. If the center node doesn't have a child node then it's a dead end leaf node.

Generator Function - traversePreorder

Description: An iterator function that utilizes yield and yield*

Purpose: Iterate through the child DOM nodes in preorder center, left, right until there is none left

//GENERATOR FUNCTION MUST BE AT TOP
// TAKES PLACE OF THE getElementById API
function* traversePreOrder(node) {
  if (!node) return;

  yield node; //pause and don't return anything yet
  for (let child of node.children) {
    //delegate or point to traversePreOrder and pass in each child
    yield* traversePreOrder(child);
  }
}
Enter fullscreen mode Exit fullscreen mode

querySelector function - selectAll

querySelector MDN docs

"The querySelector() method of the Element interface returns the first element that is a descendant of the element on which it is invoked that matches the specified group of selectors."

Description: This is a callback function that utilizes the traversePreOrder generator function. Just like the MDN in the above quote docs state we need to return the children of the targeted selector

Purpose: Find the target selector style it's children and push it into an array

function selectAll(selector, root) {
  let result = [];
  for (let node of traversePreOrder(root)) {
    if (node.matches(selector)) {
      node.style.color = 'red';
      result.push(node);
    }
  }
  return result;
}
Enter fullscreen mode Exit fullscreen mode

The Driving function - myQuerySelectorAll

Description: A parent function that drives the whole mechanism using recursion with two call backs (traversePreOrder, selectAll)

Purpose: I am handling the path of a selector with and without children using the selectAll callback and default to the document.body root node if no node parameter is passed in. I have also created a newPath variable and for loop to return array of all the children

function myQuerySelectorAll(path, node = document.body) {
  let result = [];
  //BASE CASE
  if (path.length === 0) return result;

  //IF NO PATH PROVIDED START FROM THE DOCUMENT.BODY
  let root = node;

  //THIS SETS THE SELECTOR PATH TO FIRST ELEMENT EX: DOCUMENT.QUERYSELECTORALL('DIV')[0]
  const selector = path[0];

  //IF THERE IS ONLY ONE SELECTOR IN PATH, TRAVERSE USING SELECTALL FUNCTION
  if (path.length === 1) return selectAll(selector, root);

  //CHECK IF THE CURRENT NODE MATCHES THE CURRENT SELECTOR PATH  AND SLICE OFF IT'S PARENT  FOR SUBSEQUENT SELECTORS
  const newPath = root.matches(selector) ? path.slice(1) : path;
  // LOOP THROUGH THE ROOT CHILDREN RETURN ARRAY OF NODES AND ADD ANY CAUGHT IN THE RECURSION
  for (let child of root.children) {
    result = [...result, ...myQuerySelectorAll(newPath, child)];
  }
  // NOTHING FOUND
  return result;
}
const findNestedPTags = myQuerySelectorAll(['div', 'p']);
// const findNestedX = myQuerySelectorAll(['div','p.x']);

console.log('findNestedPTags', findNestedPTags);
// console.log('findNested', findNestedX);
Enter fullscreen mode Exit fullscreen mode

HTML

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <link rel="stylesheet" href="style.css" />
    <title>DFS</title>
  </head>
  <body>
    <div>
      <h1>Traversing The DOM With Recursion</h1>
      Parent Div main container
      <div class="sibling">
        1 level deep #1 sibling has children
        <div>
          2 level deep
          <div>
            3 level deep
            <div>
              4 level deep container of p tag children
              <p>This is the target p tag to style red</p>
              <p>This is the target p tag to style red</p>
              <p>This is the target p tag to style red</p>
              <p>This is the target p tag to style red</p>
            </div>
          </div>
        </div>
      </div>
      <div class="sibling">1 level deep #2 sibling no children</div>
      <div class="sibling">1 level deep #3 sibling no children</div>
      <div class="sibling">
        1 level deep #4 sibling has children
        <div>
          2 level deep
          <div>
            3 level deep
            <div>
                4 level deep 
                <div>
                    5 level deep container of p tag children
                    <p>This is the target p tag to style red</p>
                    <p class="x" id="x">This is the target p tag to style red--test</p>
                    <p>This is the target p tag to style red</p>
                    <p>This is the target p tag to style red</p>
                </div>
            </div>
          </div>
        </div>
      </div>
      <div class="sibling">1 level deep #5 sibling no children</div>
    </div>
    <script src="index.js"></script>
  </body>
</html>

Enter fullscreen mode Exit fullscreen mode

CSS

@import url('https://fonts.googleapis.com/css?family=Roboto+Mono&display=swap');
* {
  box-sizing: border-box;
}
/* Body centers the column at 100 vh and hide scrollbars */
body {
  background-color: #c4c1c6;
  color: whitesmoke;
  font-family: 'Roboto Mon0', sans-serif;
  margin: 0;
  display: flex;
  align-items: center;
  justify-content: center;
  height: 100vh;
  overflow: hidden;
}

h1{
    text-align: center;
}
Enter fullscreen mode Exit fullscreen mode

Notes:

There are several improvements needed such as abstracting the styling as an argument in the selecAll function and adding more logic to the selectAll function to not just handle selectors but node id's as well. The generator function could also be replaced with async await. All comments are welcome

Links

yield
yield*
querySelector
slice

❤️❤️❤️

repo

Social

Twitter
Linkedin
Portfolio
Github

🤘
Happy Coding

Top comments (1)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

Create an Account!
Now it's your turn!
 
🗒 Share a tutorial
🤔 Reflect on your coding journey
❓ Ask a question

Create an account to join hundreds of thousands of DEV members on their journey.