Ben Pickles. Saying stuff about stuff.

Finding a DOM node’s common ancestor using JavaScript

I recently ran into a problem where I needed a way to find the common ancestor of two DOM nodes (using JavaScript). I wasn't happy with the accepted answer I found on Stack Overflow so I made my own.

function parents(node) {
  var nodes = []
  for (; node; node = node.parentNode) {
    nodes.push(node)
  }
  return nodes
}

function commonAncestor(node1, node2) {
  var parents1 = parents(node1)
  var parents2 = parents(node2)

  for (var i = 0; i < parents1.length; i++) {
    if (parents2.indexOf(parents1[i]) > -1) return parents1[i]
  }

  throw "No common ancestor!"
}

Unfortunately, after working with Mr Blimke for so long this first algorithm is no longer good enough for me as it has an efficiency of O(N1 * N2) - basically O(N2).

So I thought a little longer and made some simple changes. The new algorithm has efficiency O(N) and a bonus of detecting whether the nodes are actually related before attempting to compute anything.

function parents(node) {
  var nodes = []
  for (; node; node = node.parentNode) {
    nodes.unshift(node)
  }
  return nodes
}

function commonAncestor(node1, node2) {
  var parents1 = parents(node1)
  var parents2 = parents(node2)

  if (parents1[0] != parents2[0]) throw "No common ancestor!"

  for (var i = 0; i < parents1.length; i++) {
    if (parents1[i] != parents2[i]) return parents1[i - 1]
  }
}

The thing is, I imagine there are even more efficient solutions but this one will have to do for now! Anyway I added it as an answer to the original Stack Overflow question so mod it up if you like it!

Posted on

Tweet