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

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

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