19.find-corresponding-node-in-two-identical-DOM-tree.md

19. find corresponding node in two identical DOM tree

Problem

https://bigfrontend.dev/problem/find-corresponding-node-in-two-identical-DOM-tree

Problem Description

Given two same DOM tree A, B, and an Element a in A, find the corresponding Element b in B.

By corresponding, we mean a and b have the same relative position to their DOM tree root.

follow up

This could a problem on general Tree structure with only children.

Could you solve it recursively and iteratively?

Could you solve this problem both with special DOM api for better performance?

What are the time cost for each solution?

Recursive Solution

/**
 * @param {HTMLElement} rootA
 * @param {HTMLElement} rootB - rootA and rootB are clone of each other
 * @param {HTMLElement} nodeA
 */
const findCorrespondingNode = (rootA, rootB, targetNode) => {
  if (rootA === targetNode) {
    return rootB;
  }

  for (let i = 0; i < rootA.childNodes.length; i++) {
    const result = findCorrespondingNode(
      rootA.childNodes[i],
      rootB.childNodes[i],
      targetNode
    );
    if (result) {
      return result;
    }
  }
  return null;
};

Iterative Solution

/**
 * @param {HTMLElement} rootA
 * @param {HTMLElement} rootB - rootA and rootB are clone of each other
 * @param {HTMLElement} nodeA
 */
const findCorrespondingNode = (rootA, rootB, target) => {
  let stackA = [rootA];
  let stackB = [rootB];

  while (stackA.length > 0) {
    const nodeA = stackA.pop();
    const nodeB = stackB.pop();

    if (nodeA === target) {
      return nodeB;
    }

    stackA.push(...nodeA.childNodes);
    stackB.push(...nodeB.childNodes);
  }

  return;
};

Solution with DOM API parentNode

/**
 * @param {HTMLElement} rootA
 * @param {HTMLElement} rootB - rootA and rootB are clone of each other
 * @param {HTMLElement} nodeA
 */
const findCorrespondingNode = (rootA, rootB, target) => {
  const path = [];
  let node = target;
  while (node !== rootA) {
    const parentNode = node.parentNode;
    const childNodes = Array.from(parentNode.childNodes);
    path.push(childNodes.indexOf(node));
    node = parentNode;
  }

  return path.reduceRight((node, index) => node.childNodes[index], rootB);
};

Usage

const rootA = {
  value: "A",
  childNodes: [
    {
      value: "B",
      childNodes: [
        {
          value: "C",
          childNodes: [],
        },
      ],
    },
  ],
};

const rootB = {
  value: "A",
  childNodes: [
    {
      value: "B",
      childNodes: [
        {
          value: "C",
          childNodes: [],
        },
      ],
    },
  ],
};

const targetNode = rootA.childNodes[0].childNodes[0];

console.log(findCorrespondingNode(rootA, rootB, targetNode));

Explanation

Let's break down the findCorrespondingNode function and its usage:

1. Function Definition: The findCorrespondingNode function takes three arguments: nodeA, nodeB, and targetNode. It's designed to find a node in nodeB that corresponds to targetNode in nodeA, assuming nodeA and nodeB have the same structure.

2. Base Cases: If nodeA is the targetNode, it returns nodeB. If nodeA has no child nodes, it returns null because there's no corresponding node in nodeB.

3. Recursion: If nodeA is not the targetNode and it has child nodes, it recursively calls findCorrespondingNode for each pair of child nodes in nodeA and nodeB. If a recursive call returns a non-null result, it returns that result.

4. Usage: The usage example creates two identical tree structures nodeA and nodeB, each with a root node and a single child node that also has a single child node. It then calls findCorrespondingNode with nodeA, nodeB, and the first child node of nodeA as the targetNode.

5. Output: The output of the function call is the first child node of nodeB, which corresponds to the targetNode in nodeA. This is logged to the console.

This findCorrespondingNode function can be used to find corresponding nodes in two tree structures that have the same structure. It uses a depth-first search strategy, checking the current node before checking the child nodes.

Reference

Problem Discuss