Lowest Common Ancestor

Given two nodes, get the lowest common ancestor of the tree.

var Tree = function(){
this.children = [];
};
Tree.prototype.getClosestCommonAncestor = function(n1, n2){
// TODO
}

To start, consider how to break this large problem up into subproblems. What information about these two nodes, if I knew, would enable me to easily solve this? Well, if I had the path of each of these two nodes, from the root of the tree, to the end of the node, all I would need to do is compare the paths and find the last one in common.

So let’s start by writing a getAncestorPath.

Tree.prototype.getAncestorPath = function(target) {

}
// Example
var queen = new Tree();
var jack = new Tree();
queen.addChild(jack);
queen.getAncestorPath(jack); // => [queen, jack]

If we’re trying to get path from a root to target and we’re traversing the tree, what are the two cases we have to consider?

Have we found our target?

  1. If yes, return
  2. If no, keep iterating

Thus, we can fill in our function as such (pay attention to the guiding principles in the comments!):

Tree.prototype.getAncestorPath = function(target, path = []) {
// Do we have a solution?
if (this === target) {
// Deal with the fact that we have a solution
} else {
// Iterate over possible decisions (in this case, children)
for (var i = 0; i < this.children.length; i++) {
// Make the decision and check if its valid recursively
}
}
}

We have our skeleton. Now we can start filling things in:

Tree.prototype.getAncestorPath = function(target, path = []) {
// Do we have a solution?
if (this === target) {
// Deal with the fact that we have a solution
// Add to our path
path.unshift(this);
return path;
} else {
// Iterate over possible decisions (in this case, children)
for (var i = 0; i < this.children.length; i++) {
// Make the decision and check if its valid recursively
if (this.children[i].getAncestorPath(target, path)) {
path.unshift(this);
return path;
}
}
}
return null;
}

OK, phew. Now that we have this subproblem done, we can use it to help solve our closestCommonAncestor problem:

Tree.prototype.getClosestCommonAncestor = function(n1, n2){
// Get paths of n1 and n2
var path1 = this.getAncestorPath(n1)
var path2 = this.getAncestorPath(n2)
if (!path1 || !path2) return null
ancestor = null;

// Get the shorter length
var shorterLength = Math.min(path1.length, path2.length)

// Compare each index and get the furthest common index
for (var i = 0; i < shorterLength; i++) {
if (path1[i] === path2[i]) {
ancestor = path[i]
}
}

return ancestor;
}

This problem is a type of decision tree problem. All decision tree problems generally have the following framework:

  1. Check if you have a solution
    - If so, deal with the fact that you have a solution
  2. Iterate over possible decisions
    - Make the decision
    - Recursively check if the decision you made is valid
    - Go to the next decision