Struggling with and then Successfully Implementing Recursive, Depth-first Traversal of the DOM

Hayden Betts
Sep 4, 2018 · 3 min read

I was recently tasked with re-implementing the getElementsByClassName method on the Document web interface from scratch.

In order to fully implement getElementsByClassName, it is necessary to traverse every node in the DOM, each time checking whether that node is of the class you are looking for.

In my first attempt at implementing the function, it looked like this:

// Attempt #1
var getElementsByClassName = function(className) {
var matchingNodes = [];
function traverseDOM(node) {
if (node.classList && node.classList.contains(className)) {
matchingNodes.push(node);
}

if (node.firstChild) {
traverseDOM(node.firstChild);
} else if (node.nextSibling) {
traverseDOM(node.nextSibling);
}
}
traverseDOM(document.body); return matchingNodes;
};

This function seemed to work in about half the cases I tested it on. I spent quite a few hours confused why it didn’t work in all cases.

As I was trying to to determine the problem with the function, I created the following mock-ups of example HTML trees I was passing into my function.

Example #1

The red line indicates that path my Attempt #1 at implementing getElementsByClassName takes when traversing the sample DOM.

When passed the tree in Example #1, my Attempt #1 behaves as I expected it to.

It traverses every node in the DOM successfully using the conditional built into it:

if (node.firstChild) {
traverseDOM(node.firstChild);
}
else if (node.nextSibling) {
traverseDOM(node.nextSibling);
}
// *implicitly* if neither of these conditions is met, you have found a node with no children, and no siblings. You can safely pop this instance of traverseDOM off the call-stack.

Attempt #1 also works for the following Example #2:

The red line indicates that path my Attempt #1 at implementing getElementsByClassName takes when traversing the sample DOM.

However, I ran into trouble with Example #3:

Here was my understanding on how my Attempt #1 at implementing getElementsByClassName worked in this case.

The red-line indicates my (incorrect) perception of how Attempt #1 at getElementsByClassName traversed the DOM.

At the crucial time-step, I expected my function to execute the below bolded bit of code:

if (node.firstChild) {
traverseDOM(node.firstChild);
}
else if (node.nextSibling) {
traverseDOM(node.nextSibling);
}

// *implicitly* if neither of these conditions is met, you have found a node with no children, and no siblings. You can safely pop this instance of traverseDOM off the call-stack.

However, I misunderstood how else if statements work in Javascript.

Per this SE answer “else if statements specify a new condition to test, if the the first condition is false.

My unstated assumption had been that it would be possible to ‘fall through’ an if statement and then and if-else statement. Since this is not true, my function would stopped traversing the DOM at this point:

In other words, my Attempt #1 at getElementsByClassName did not fully traverse trees that contained nodes with both children and siblings. It was an (unlucky) coincidence that the function happened to work for Example #1 and Example #2.

I fixed the issue by simply changing the else if statement to an if statement as follows in Attempt #2. This ensures that the function will not stop traversing the tree when it encounters a node that has both children and siblings.

// Attempt #2
var getElementsByClassName = function(className) {
var matchingNodes = [];
function traverseDOM(node) {
if (node.classList && node.classList.contains(className)) {
matchingNodes.push(node);
}

if (node.firstChild) {
traverseDOM(node.firstChild);
}
if (node.nextSibling) {
traverseDOM(node.nextSibling);
}
}
traverseDOM(document.body);return matchingNodes;
};
Hayden Betts

Written by

Aspiring Web Dev | Ex-Technical Writer @Yardi | @haydenbetts

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade