AlgoDaily - Lowest Common Ancestor

Then, we'd repeat this for 9 (9 -> 6).

See something in common? The final nodes of both paths ended up being the same (node 6). We are thus able to conclude that 6 is the lowest common ancestor, as it's by definition the highest node they have in common (note that there can more than one shared ancestor, but this is the lowest in the branching chain).

If we think about possible solutions, what do we need to do? The solution we want is a traversal to find the first difference in node-to-root path. Is there anything about BST properties that could help us traverse upwards while starting from the root?

Let's revisit some Binary Search Tree properties and start with a basic question about binary trees:

xxxxxxxxxx
  console.log('PASSED: ' + '`lowestCommonAncestor` should be a function');
 
var assert = require('assert');
​
function lowestCommonAncestor(root, node1, node2) {
  // Fill in this method
  return root;
}
​
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}
​
// Regular binary trees
var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);
​
var tree2 = new Node(5);
tree2.left = new Node(10);
tree2.left.left = new Node(17);
tree2.left.right = new Node(3);
tree2.right = new Node(8);
​
// Binary search trees
var tree3 = new Node(6);
tree3.left = new Node(3);

OUTPUT

Results will appear here.