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)