## 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(N_{1} * N_{2}) - basically O(N^{2}).

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