Identical DOM Trees

Medium

Prompt

Implement a function identicalDOMTrees that checks if two DOM trees are identical or not. The function takes two DOM nodes as the root nodes of two DOM trees and returns a boolean result.

Two DOM trees are considered identical if they are structurally similar, and the DOM nodes on one tree have the exact same attributes as the nodes on the same relative position on the other tree.

Example

Tree A and Tree B are considered the same.

<!-- Tree A -->
<div>Hello World</div>

<!-- Tree B -->
<div>Hello World</div>

Tree C and Tree D are not considered the same.

<!-- Tree C -->
<div class="header">Hello World</div>

<!-- Tree D -->
<div id="foo">Hello World</div>

Playground

Solution

Explanation

Hey there! Let's break down this DOM tree comparison function step by step. When we're working with the DOM, we're essentially dealing with a tree structure, and comparing trees is a perfect use case for recursion.

Before we dive into the code, let's understand what it means for two DOM trees to be identical:

• They must have the same structure (same hierarchy of nodes)
• Each pair of corresponding nodes must be of the same type
• Element nodes must have the same tag name
• Element nodes must have the same attributes with the same values
• Text nodes must have the same content

Our identicalDOMTrees function uses a recursive approach to compare two DOM trees. Here's how it works:

1. Node Type Comparison

First, we check if the nodes are of the same type. In the DOM, different types of nodes have different numeric values:

• Element nodes (like <div>) have nodeType of 1
• Text nodes (the actual text content) have nodeType of 3
• Comments have nodeType of 8
• And a few others you'll rarely encounter

If the node types don't match, we immediately know the trees aren't identical.

if (nodeA.nodeType !== nodeB.nodeType) {
  return false;
}

2. Text Node Handling

If both nodes are text nodes, we simply compare their text content. Text nodes are leaf nodes in the DOM tree, so we don't need to check children.

if (nodeA.nodeType === Node.TEXT_NODE) {
  return nodeA.textContent === nodeB.textContent;
}

3. Element Comparison

Tag names: If the elements have different tag names, they're not identical.

if (nodeA.tagName !== nodeB.tagName) {
  return false;
}

Number of children: If one node has more children than the other, they can't be identical.

if (nodeA.childNodes.length !== nodeB.childNodes.length) {
  return false;
}

Number of attributes: If the elements have different numbers of attributes, they're not identical.

if (nodeA.attributes.length !== nodeB.attributes.length) {
  return false;
}

Attribute values: Here we're checking if every attribute in nodeA has the same value in nodeB. The every() method is perfect for this - it returns true only if all checks pass.

const hasSameAttributes = nodeA
  .getAttributeNames()
  .every(
    (attrName) =>
      nodeA.getAttribute(attrName) ===
      nodeB.getAttribute(attrName)
  );

if (!hasSameAttributes) {
  return false;
}

4. Recursive Child Comparison

Finally, we recursively compare each child node. We're using Array.prototype.every.call() because childNodes is not a true array but a NodeList. This checks that all corresponding pairs of child nodes are identical.

return Array.prototype.every.call(
  nodeA.childNodes,
  (childA, index) =>
    identicalDOMTrees(childA, nodeB.childNodes[index])
);

Time and Space Complexity

• Time Complexity: O(n), where n is the total number of nodes in the DOM tree. We visit each node exactly once.
• Space Complexity: O(h), where h is the height of the DOM tree. This comes from the recursive call stack.

Real World Application

1. Testing libraries use similar algorithms to compare expected and actual DOM output
2. Virtual DOM implementations (like in React) use tree diffing to determine what parts of the DOM need to be updated