DOM Question #7 - Circular Reference

Detect cycles in a DOM tree (circular references) DOM is a tree which means it should have hierarchical structures, which means it should not have circular reference. But circular reference can still occur due to Improper DOM manipulation: eg. If a node's child references the parent node, you would introduce a cycle in what was supposed to be a tree structure. const parent = document.createElement('div'); const child = document.createElement('div'); // Setting up a circular reference parent.appendChild(child); child.appendChild(parent); // This creates a cycle How can we detect circular reference? We traverse the DOM and track visited nodes. If we encounter node which is already visited then DOM has circular reference. function detectCycle(root){ const visitedNodes = new Set(); function traverse(node){ if(visitedNode.has(node)){ return true; } visitedNodes.add(node); for(let child of node.children){ if(traverse){ return true; } } return false; } return traverse(root) } What is time complexity of this code? To traverse tree we used DFS, so we visit each node once. Considering N is number of nodes time complexity of this will become O(N)

Mar 2, 2025 - 15:26

Detect cycles in a DOM tree (circular references)

DOM is a tree which means it should have hierarchical structures, which means it should not have circular reference.

But circular reference can still occur due to

Improper DOM manipulation: eg. If a node's child references the parent node, you would introduce a cycle in what was supposed to be a tree structure.

const parent = document.createElement('div');
const child = document.createElement('div');

// Setting up a circular reference
parent.appendChild(child);
child.appendChild(parent); // This creates a cycle

How can we detect circular reference?

We traverse the DOM and track visited nodes. If we encounter node which is already visited then DOM has circular reference.

function detectCycle(root){
 const visitedNodes = new Set();

 function traverse(node){
  if(visitedNode.has(node)){
    return true;
  }

  visitedNodes.add(node);

  for(let child of node.children){
    if(traverse){
      return true;
    }
  }
 return false;
 }
  return traverse(root)
}

What is time complexity of this code?
To traverse tree we used DFS, so we visit each node once.
Considering N is number of nodes time complexity of this will become O(N)