Using DFS to implement getElementById

supergentle — Fri, 29 Jan 2021 19:42:12 +0000

Being a front-end engineer, there could be less chances on implementing data structure and advanced algorithms in daily development work. However, to be hired as a front-end developer, we still need to know data structure and algorithms.

I was very skeptical on why engineers need to be evaluated on the theoretical knowledge rather than working skills and knowledge. But as time goes on and getting more experience as a developer, I do understand the importance of such theoretical knowledge.

One of the great advantages of having good understanding of data structure is that when analyzing a system, one can identify what data structure could be a best fit. And after the data structure is set, one can find what could be the best algorithm to be used as well if needed.

For examples, let's think about HTML DOM. For people who know data structure, they will instantly think that HTML DOM is in tree structure. And furthermore, let's make an assumption that browsers do not provide DOM API. In order to find a specific DOM element in the HTML, one can guess what the best algorithm would be to implement that search functionality. In this case, DFS/BFS. For people who do not contain the knowledge of data structure and algorithm, this would be too challenging task or they could end up poorly-performing solution.

Here is a few lines of code to implement DFS that traverses a tree in Javascript.

/**
 * @param {TreeNode} root
 * @void
 */
const dfs = (root) => {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.val); // print a node
    for (const child of node.children) { 
      stack.push(child);
    }
  }
};

And with slight changes to the DFS function, we can easily implement a search function by DOM id.

/**
 * @param {HTMLElement} root
 * @param {string} id
 * @returns {HTMLElement|null}
 */
const getElementById = (root, id) => {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (node.id === id) {
      return node;
    }
    for (const child of node.children) { 
      stack.push(child);
    }
  }
  return null;
};

It's that simple! With that in mind, you can basically implement your own DOM traversal/search functions using your knowledge in tree data structure (though your colleagues would not approve your PR).

Knowing data structure and algorithm will definitely help your daily development. It will open up more opportunities as you know more about it. And also once you have a mindset installed thinking about data structure/algorithm upfront before implementing something, it will help you to produce better and more efficient solution.

DEV Community: supergentle

Using DFS to implement getElementById