How to find the nearest common ancestors of two or more nodes?

Question

Users selects two or more elements in a HTML page. What I want to accomplish is to find those elements' common ancestors (so body node would be the common ancestor if none found before)?

P.S: It can be achieved with XPath but it is not a preferable option for me. Also it may be found with css selector parsing but I think it is a dirty method.

Obduce

Do you want the 'closest' common ancestor, or an array containing ALL common ancestors? – Cogon

only 'closest' common ancestor – Obduce

"t can be achieved with XPath but it is not a preferable option for me" -- what is the XPath solution? Why isn't it preferable for you? – Shwa

Answer 1

Try this:

function get_common_ancestor(a, b)
{
    $parentsa = $(a).parents();
    $parentsb = $(b).parents();

    var found = null;

    $parentsa.each(function() {
        var thisa = this;

        $parentsb.each(function() {
            if (thisa == this)
            {
                found = this;
                return false;
            }
        });

        if (found) return false;
    });

    return found;
}

Use it like this:

var el = get_common_ancestor("#id_of_one_element", "#id_of_another_element");

That's just rattled out pretty quickly, but it should work. Should be easy to amend if you want something slightly different (e.g. jQuery object returned instead of DOM element, DOM elements as arguments rather than IDs, etc.)

Cogon

Answer 2

Here's a pure JavaScript version that is a little more efficient.

function parents(node) {
  var nodes = [node]
  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]
  }
}

Amidst

This will fail if the DOM nodes are siblings. You should edit your code to fix that. – Nitriding

(I tried fixing it, but my change is pending approval since this is not a community wiki I think) – Nitriding

You seem to not mind at all what this is used for, but to stay on the safe side... Can I use this as part of an MIT-licensed open source library? – Doig

@JacqueGoupil - Not sure if it still matter but as the site footer says - user contributions licensed under cc by-sa 3.0 with attribution required. – Leeway

This isn't really efficient as advertised due to unshift, which is quadratic. push/reverse is linear. – Shwa

Answer 3

The solutions involving manually going through the ancestor elements are far more complicated than necessary. You don't need to do the loops manually. Get all the ancestor elements of one element with parents(), reduce it to the ones that contain the second element with has(), then get the first ancestor with first().

var a = $('#a'),
    b = $('#b'),
    closestCommonAncestor = a.parents().has(b).first();

jsFiddle example

Receipt

+1, and I stole your test case (hope you don't mind) ;-) – Renteria

+1 far better than my solution, although you had a year to think about it ;-) – Cogon

Really clean solution, though it should be marked as requiring jQuery. – Danaus

Answer 4

Here's another pure method that uses element.compareDocumentPosition() and element.contains(), the former being a standards method and the latter being a method supported by most major browsers excluding Firefox:

Comparing two nodes

function getCommonAncestor(node1, node2) {
    var method = "contains" in node1 ? "contains" : "compareDocumentPosition",
        test   = method === "contains" ? 1 : 0x10;

    while (node1 = node1.parentNode) {
        if ((node1[method](node2) & test) === test)
            return node1;
    }

    return null;
}

Working demo: http://jsfiddle.net/3FaRr/ (using lonesomeday's test case)

This should be, more or less, as efficient as possible since it is pure DOM and has only one loop.

---

Comparing two or more nodes

Taking another look at the question, I noticed the "or more" part of the "two or more" requirement had gone ignored by the answers. So I decided to tweak mine slightly to allow any number of nodes to be specified:

function getCommonAncestor(node1 /*, node2, node3, ... nodeN */) {
    if (arguments.length < 2)
        throw new Error("getCommonAncestor: not enough parameters");

    var i,
        method = "contains" in node1 ? "contains" : "compareDocumentPosition",
        test   = method === "contains" ? 1 : 0x0010,
        nodes  = [].slice.call(arguments, 1);

    rocking:
    while (node1 = node1.parentNode) {
        i = nodes.length;    
        while (i--) {
            if ((node1[method](nodes[i]) & test) !== test)
                continue rocking;
        }
        return node1;
    }

    return null;
}

Working demo: http://jsfiddle.net/AndyE/3FaRr/1

Renteria

+1 I've corrected the example because the compareDocumentPosition test never succeeded, due to its quirky behaviour. – Receipt

@lonesomeday: cheers, I forgot compareDocumentPosition returned a bitmask. I've updated the answer again after testing in Firefox. – Renteria

@AndyE a) can it be on npm. b) do you have to use labels? >_< – Dragonfly

@Raynos: Nice work :-) I used a label because I'd prefer to keep it in a single function; I was focusing on efficiency. Even the laws of Crockford allow for labels to be used, and that says a lot since they don't allow for much else. It could be on npm but most of the answers I write I do it for Stack Overflow and don't often take the extra time to submit it to other places too. – Renteria

Tidy! A version on the same performant code, also wrapping it into a jQuery.fn.commonAncestor plugin: jsfiddle.net/ecmanaut/Dv5Wj – Blasted

Answer 5

The commonAncestorContainer property of the he Range API mentioned above, alongside its selectNode, makes this a no-brainer.

Run ("display") this code in Firefox's Scratchpad or a similar editor:

var range = document.createRange();
var nodes = [document.head, document.body];  // or any other set of nodes
nodes.forEach(range.selectNode, range);
range.commonAncestorContainer;

Note that both APIs are not supported by IE 8 or below.

Condole

This doesn't work because selectNode sets the start and end for the range as the referenced node's parent, see jsfiddle.net/3FaRr/13 (should alert "thisOne", but it doesn't find the correct common ancestor). – Renteria

Answer 6

based on the answers from Andy E and AntonB

handle edge-cases: node1 == node2 and node1.contains(node2)

function getCommonParentNode(node1, node2) {
  if (node1 == node2) return node1;
  var parent = node1;
  do if (parent.contains(node2)) return parent
  while (parent = parent.parentNode);
  return null;
}

Senlac

Seems good to me (at least when looking at elements - not sure how to test TEXT nodes). jsfiddle.net/Abeeee/tjg6r1qw/11 – Aideaidedecamp

also text nodes have a node.parentNode – Senlac

Answer 7

This doesn't require much code anymore to solve:

steps:

1. grab parent of node_a
2. if parent of node_a contains node_b return parent (in our code, the parent is referenced as node_a)
3. if parent does not contain node_b we need to keep going up the chain
4. end return null

code:

function getLowestCommonParent(node_a, node_b) {
    while (node_a = node_a.parentElement) {
        if (node_a.contains(node_b)) {
            return node_a;
        }
    }

    return null;
}

Parfitt

I think that's the most clean and readable solution using pure JS. Using @lonesomeday's test case works without issue: jsfiddle.net/RayRemnant/1oagnqr0/5 – Danaus

Answer 8

You should be able to use the jQuery .parents() function and then walk through the results looking for the first match. (Or I guess you could start from the end and go backwards until you see the first difference; that's probably better.)

Circadian

To compare each element I recomend you to make a separated function. It is not so easy. The simple way (not so nice) is to compare the innerhtml of each element. The hardest (but pretty nice) is to start comparing the ids. If they are both undefined, compare the clases, if both elements have same classes (be carefull with classe's order) then you can compare the elements indexes in the body. – Pourparler

@Diego: a straight comparison between two DOM elements should be all you need, I believe – Cogon

@Pourparler because any DOM element actually in the DOM (which will be true for all the parents of an element in the DOM) only exists once, even two separate jQuery arrays will have references to the exact same objects. Thus, a simple === comparison should work fine. – Circadian

Answer 9

You can also use a DOM Range (when supported by the browser, of course). If you create a Range with the startContainer set to the earlier node in the document and the endContainer set to the later node in the document, then the commonAncestorContainer attribute of such a Range is the deepest common ancestor node.

Here is some code implementing this idea:

function getCommonAncestor(node1, node2) {
    var dp = node1.compareDocumentPosition(node2);
    // If the bitmask includes the DOCUMENT_POSITION_DISCONNECTED bit, 0x1, or the
    // DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC bit, 0x20, then the order is implementation
    // specific.
    if (dp & (0x1 | 0x20)) {
        if (node1 === node2) return node1;

        var node1AndAncestors = [node1];
        while ((node1 = node1.parentNode) != null) {
            node1AndAncestors.push(node1);
        }
        var node2AndAncestors = [node2];
        while ((node2 = node2.parentNode) != null) {
            node2AndAncestors.push(node2);
        }

        var len1 = node1AndAncestors.length;
        var len2 = node2AndAncestors.length;

        // If the last element of the two arrays is not the same, then `node1' and `node2' do
        // not share a common ancestor.
        if (node1AndAncestors[len1 - 1] !== node2AndAncestors[len2 - 1]) {
            return null;
        }

        var i = 1;
        for (;;) {
            if (node1AndAncestors[len1 - 1 - i] !== node2AndAncestors[len2 - 1 - i]) {
                // assert node1AndAncestors[len1 - 1 - i - 1] === node2AndAncestors[len2 - 1 - i - 1];
                return node1AndAncestors[len1 - 1 - i - 1];
            }
            ++i;
        }
        // assert false;
        throw "Shouldn't reach here!";
    }

    // "If the two nodes being compared are the same node, then no flags are set on the return."
    // http://www.w3.org/TR/DOM-Level-3-Core/core.html#DocumentPosition
    if (dp == 0) {
        // assert node1 === node2;
        return node1;

    } else if (dp & 0x8) {
        // assert node2.contains(node1);
        return node2;

    } else if (dp & 0x10) {
        // assert node1.contains(node2);
        return node1;
    }

    // In this case, `node2' precedes `node1'. Swap `node1' and `node2' so that `node1' precedes
    // `node2'.
    if (dp & 0x2) {
        var tmp = node1;
        node1 = node2;
        node2 = tmp;
    } else {
        // assert dp & 0x4;
    }

    var range = node1.ownerDocument.createRange();
    range.setStart(node1, 0);
    range.setEnd(node2, 0);
    return range.commonAncestorContainer;
}

Erwinery

Answer 10

This is a generalized take on lonesomeday's answer. Instead of only two elements it will take a full JQuery object.

function CommonAncestor(jq) {
    var prnt = $(jq[0]);
    jq.each(function () { 
        prnt = prnt.parents().add(prnt).has(this).last(); 
    });
    return prnt;
}

Helsinki

Answer 11

Somewhat late to the party, but here's an elegant jQuery solution (since the question is tagged jQuery) -

/**
 * Get all parents of an element including itself
 * @returns {jQuerySelector}
 */
$.fn.family = function() {
    var i, el, nodes = $();

    for (i = 0; i < this.length; i++) {
        for (el = this[i]; el !== document; el = el.parentNode) {
            nodes.push(el);
        }
    }
    return nodes;
};

/**
 * Find the common ancestors in or against a selector
 * @param selector {?(String|jQuerySelector|Element)}
 * @returns {jQuerySelector}
 */
$.fn.common = function(selector) {
    if (selector && this.is(selector)) {
        return this;
    }
    var i,
            $parents = (selector ? this : this.eq(0)).family(),
            $targets = selector ? $(selector) : this.slice(1);
    for (i = 0; i < $targets.length; i++) {
        $parents = $parents.has($targets.eq(i).family());
    }
    return $parents;
};

/**
 * Find the first common ancestor in or against a selector
 * @param selector {?(String|jQuerySelector|Element)}
 * @returns {jQuerySelector}
 */
$.fn.commonFirst = function(selector) {
    return this.common(selector).first();
};

Sirius

@TrueBlueAussie I actually improved my code somewhat since this, so updated on here - the biggest issue with your sample is simply that the .id should be .attr("id") or [0].id (since it's jQuery) :-) – Sirius

Cool. I used that example from another answer here. Should have spotted that error. It would be worth speed testing this against the simplest a.parents().has(b).first() answer. – Font

The problem with .parents() is that it excludes itself (so you need .addBack() on the end) - which is more expensive than creating it manually as I now do with .family() - might be worth testing .parents().addBack() against .family() though :-P – Sirius

Answer 12

Somewhat late to the party, here's a JavaScript ES6 version that uses Array.prototype.reduce() and Node.contains(), and can take any number of elements as parameters:

function closestCommonAncestor(...elements) {
    const reducer = (prev, current) => current.parentElement.contains(prev) ? current.parentElement : prev;
    return elements.reduce(reducer, elements[0]);
}

const element1 = document.getElementById('element1');
const element2 = document.getElementById('element2');
const commonAncestor = closestCommonAncestor(element1, element2);

Bausch

Looks awesome but doesn't seem to work. Try <div class="test1"><div class="test"><p>Foo</p></div><div><p>Baz</p></div></div>. The correct common ancestor of the two p elements is div.test1 but this function returns div.test instead. – Shwa

Answer 13

Here is a dirtier way of doing this. It's easier to understand but requires dom modification:

function commonAncestor(node1,node2){
        var tmp1 = node1,tmp2 = node2;
        // find node1's first parent whose nodeType == 1
        while(tmp1.nodeType != 1){
            tmp1 = tmp1.parentNode;
        }
        // insert an invisible span contains a strange character that no one 
        // would use
        // if you need to use this function many times,create the span outside
        // so you can use it without creating every time
        var span = document.createElement('span')
            , strange_char = '\uee99';
        span.style.display='none';
        span.innerHTML = strange_char;
        tmp1.appendChild(span);
        // find node2's first parent which contains that odd character, that 
        // would be the node we are looking for
        while(tmp2.innerHTML.indexOf(strange_char) == -1){
            tmp2 = tmp2.parentNode; 
        }                           
        // remove that dirty span
        tmp1.removeChild(span);
        return tmp2;
    }

Supercharge

What's the purpose of a dirtier solution? kic (keep it complicated) principle? – Sequestered

Answer 14

PureJS

function getFirstCommonAncestor(nodeA, nodeB) {
    const parentsOfA = this.getParents(nodeA);
    const parentsOfB = this.getParents(nodeB);
    return parentsOfA.find((item) => parentsOfB.indexOf(item) !== -1);
}

function getParents(node) {
    const result = [];
    while (node = node.parentElement) {
        result.push(node);
    }
    return result;
}

Sequestered

Answer 15

did not liked any of the answers above(want pure javascript and one function). that worked perfectly for me,efficient and also easier to understand:

    const findCommonAncestor = (elem, elem2) => {
      let parent1 = elem.parentElement,parent2 = elem2.parentElement;
      let childrensOfParent1 = [],childrensOfParent2 = [];
      while (parent1 !== null && parent2 !== null) {
        if (parent1 !== !null) {
          childrensOfParent2.push(parent2);
          if (childrensOfParent2.includes(parent1)) return parent1;
        }
        if (parent2 !== !null) {
          childrensOfParent1.push(parent1);
          if (childrensOfParent1.includes(parent2)) return parent2;
        }
        parent1 = parent1.parentElement;
        parent2 = parent1.parentElement;
      }
      return null;
    };

Messiaen

Answer 16

Here is a better and shorter way of finding the common ancestor of two or more elements:

// find the common ancestor of two nodes
const findFirstCommonAncestor = (nodeA, nodeB) => {
   if (nodeA.contains(nodeB)) return nodeA;
   if (nodeB.contains(nodeA)) return nodeB;


   const range = new Range();
   range.setStartBefore(nodeA);
   range.setEndAfter(nodeB);
   if (range.collapsed) {
      range.setStartBefore(nodeB);
      range.setEndAfter(nodeA);
   }
   return range.commonAncestorContainer;
};


// find the common ancestor of multiple nodes
const firstFirstCommonAncestorMultiple = (nodes) =>
   nodes.reduce((acc, node) => (acc === node ? acc : findFirstCommonAncestor(acc, node)), nodes[0]);

Devolution

Answer 17

Did anyone say "recursion" yet?

function domNodeCommonAncestor(na, nb){
    if (na.contains(nb)){
        return na;
    } else {
        return domNodeCommonAncestor(na.parentElement, nb);
    }
}

Number