Find corresponding node in an identical DOM tree

The following question derives it source from a Facebook interview ( source ). It is one of the most asked questions in the first (screening) round of frontend interviews.

Without any further ado, let's jump onto the question.

Question

Given two identical DOM trees A and B with their root nodes rootA and rootB respectively, and a node nodeA in A, find the node nodeB at the corresponding position in B. By corresponding, I mean nodeA and nodeB should have the same position relative to their respective DOM tree root.

This question holds the fame for not being understood when read the first time (just kidding 😛). Read the question again and try to understand the problem statement.

The attached image sure helps. But most of the times, the question is asked verbally and not via some written medium. So, there are fair chances that you have to imagine the picture.

Churning

Okay, so I have two identical trees, which means design wise the trees are same. Now, nodes at trees can have different values, but for each node in A, there will be a corresponding node in B at a similar position relative to its root and vice versa. Hmm..got it. So, I have to find the depth and the exact position where nodeA is located in A. I need some kind of a path from rootA to nodeA. Once I have got it, I can iterate on the same path from rootB and reach the corresponding nodeB in B. Bingo! ✨🚀

50% of your work is done

Follow up questions to the interviewer

As it is not a generic tree, but a DOM, can I use DOM APIs to traverse the tree?

Mostly it is a yes, because the main motive of this question is to test your logic and approach towards the problem and not how you choose to go about writing your solution.

Solution

const findCorrespondingNode = (rootA, rootB, nodeA) => {
  // to get the path from rootA to nodeA
  const pathToNodeA = getPath(rootA, nodeA);

  // get to nodeB by iterating over pathToNodeA
  return getNodeFromPath(rootB, pathToNode);
}

This is what you wish to do.

It is always better to write functions for different tasks to maintain separation of concern. Breaking a bigger problem into chunks of smaller ones. It helps maintain clarity in your head amidst the chaos of the interview. Now, let us write these two functions one by one.

function getPath(root, node) {
  const path = [];

  // going from bottom to top
  while (node !== root) {
    const parent = node.parentElement;
    const children = Array.from(parent.children);
    // finding the index of the current node wrt its parent
    const nodeIndex = children.indexOf(node);
    path.push(nodeIndex);
    node = parent;
  }

  return path;
}

Now, I have the path from rootA to nodeA. But in reverse order. Let's write the function to iterate over a given path from rootB to reach nodeB.

function getNodeFromPath(node, path) {
  const pathToWalk = [...path];

  while (pathToWalk.length > 0) {
    // using pop, we made up for the reverse order of path
    node = node.children[pathToWalk.pop()];
  }

  return node;
}

There you go!

Follow up questions

1. This is an iterative approach that you have taken. Can you solve it recursively?

2. What are the time cost for each solution?

Please think of these answers and answer in the comment section below 😊

If you liked what you read 🧑‍🏫 and got to learn new things, do hit like 👍 and subscribe 🔖to my newsletter to get instantly notified whenever I drop in new content. And don't forget to follow 🚀 me on

Hashnode - Rajat Jain

Twitter - @rajat_codes

Instagram - @javascript_to_the_rescue

LinkedIn - Rajat Jain