Skip to content

Instantly share code, notes, and snippets.

@benpickles

benpickles/common-ancestor.js

Last active August 9, 2020 13:49
Show Gist options
  • Save benpickles/4059636 to your computer and use it in GitHub Desktop.
Save benpickles/4059636 to your computer and use it in GitHub Desktop.
Download ZIP
Written as a response to a Stack Overflow question "How to find the nearest common ancestors of two or more nodes?" https://stackoverflow.com/a/5350888/194664
Raw
common-ancestor.js
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]
}
}
Raw
test.html
<!DOCTYPE html>
<html>
<head>
<title>Common Ancestor Tests</title>
<link rel="stylesheet" href="http://code.jquery.com/qunit/qunit-1.10.0.css">
<script src="./common-ancestor.js"></script>
</head>
<body>
<div id="qunit"></div>
<script src="http://code.jquery.com/qunit/qunit-1.10.0.js"></script>
<script src="./test.js"></script>
</body>
</html>
Raw
test.js
function createElement(parent) {
var elem = document.createElement("div")
if (parent) {
parent.appendChild(elem)
}
return elem
}
var root = createElement() // .
var elem1 = createElement(root) // ├── elem1
var elem2 = createElement(elem1) // | ├── elem2
var elem3 = createElement(elem1) // | └── elem3
var elem4 = createElement(elem3) // | └── elem4
var elem5 = createElement(root) // └── elem5
test("same parent", function() {
ok(commonAncestor(elem1, elem5) === root)
})
test("same parent but deeper", function() {
ok(commonAncestor(elem4, elem5) === root)
})
test("direct child of the other", function() {
ok(commonAncestor(elem1, elem2) === elem1)
})
test("grandchild of the other", function() {
ok(commonAncestor(elem1, elem4) === elem1)
})
test("when there's no common ancestor", function() {
var separate = createElement()
var thrown = false
try {
commonAncestor(elem3, separate)
} catch(e) {
thrown = true
}
ok(thrown)
})
Copy link

ghost commented May 17, 2014

Hi Ben,

There is a small typo in test.js. To match the comment, it should be:

var elem3 = createElement(elem1)

(i.e. elem3 is a child of elem1)

@benpickles
Copy link
Author

Thanks!

@DavidA94
Copy link

Commenting is a wonderful feature of every language:

function parents(node){
    // Place the first node into an array
    var nodes = [node];

    // As long as there is a node
    for(; node; node = node.parentNode){
        // Place that node at the beginning of the array
        // This unravels the tree into an array with child/parents only
        nodes.unshift(node)
    }
    // Return the array
    return nodes;
}

function commonAncestor(node1, node2){
    // Get the hierarchy arrays
    var parents1 = parents(node1);
    var parents2 = parents(node2);

    /* At this point we have two hierarchies. Although DOM can go x steps up to
    ** a common parent node, top down will be equal for a common ancestor, as 
    ** the difference to the top is only after we break past the common ancestor.
    ** After that, the common node has the same parent as the other node, so it's
    ** the same all the way to the top. (If that doesn't make sense, thing about
    ** it, and maybe draw it out).    
    */

    // Ensure we have found a common ancestor, which will be the first one if anything
    if(parents1[0] != parents2[0]) return null;

    /* Otherwise, traverse down the hierarchy until we reach where they're no longer
    ** the same. Then return one up, which is the closest, common ancestor.
    */
    for(var i = 0; i < parents1.length; ++i){
        // If we found the split, return the one above it
        if(parents1[i] != parents2[i]) return parents1[i - 1];
    }

    // Formality, even though we'll never make it this far
    return null;
}

No, I don't over comment. I have no clue what you're talking about. ;)

@jul-sh
Copy link

jul-sh commented Nov 26, 2019 •
edited
Loading

Version that accepts more than two nodes

function getParents (node) {
  // Place the first node into an array
  const nodes = [node]

  // As long as there is a parent node that we have yet to add
  while (nodes[nodes.length - 1].parentNode) {
    // Place that node at the end of the array
    // This unravels the tree into an array with child/parents only.
    nodes.push(node)
  }

  // Reverse the array so it starts from the highest ancestor, all the way down
  // to our node.
  nodes.reverse()

  return nodes
}

function isArrayOfIdenticalItems (array) {
  return array.every(item => item === array[0])
}

function getLastCommonAncestor (nodes) {
  // Get an array whose items are arrays of parents
  const arrayOfParents = nodes.map(node => getParents(node))

  /* Although DOM can go many steps up to
   ** a common parent node, top down will be equal for a common ancestor, as
   ** the difference to the top is only after we break past the common ancestor.
   ** After that, the common node has the same parent as the other node, so it's
   ** the same all the way to the top. (If that doesn't make sense, thing about
   ** it, and maybe draw it out).
   */

  // Ensure we have a common ancestor, it will be the first one if anything
  const topMostAncestors = arrayOfParents.map(parents => parents[0])

  
  if (!isArrayOfIdenticalItems(topMostAncestors)) {
    // We do not have a common ancestor, let's throw
    throw new Error('No common ancestor!')
  }

  // Let's move down the ancestor from the top to the bottom
  for (let index = 1; index < arrayOfParents[0].length; index++) {
    const parentsAtIndex = arrayOfParents.map(parents => parents[index])

    if (isArrayOfIdenticalItems(parentsAtIndex)) {
      // It's a common ancestor, let's continue the loop
    } else {
      // It's not a common ancestor, let's hence the common ancestor must be
      // the one from the previous loop
      return arrayOfParents[0][index - 1]
    }
  }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment