{"size": 1470, "ext": "js", "max_stars_repo_path": "edition4/js/ch04/4-6.js", "max_stars_repo_name": "kgraves/ctci", "max_stars_repo_stars_event_min_datetime": null, "max_stars_repo_stars_event_max_datetime": null, "max_issues_repo_path": "edition4/js/ch04/4-6.js", "max_issues_repo_name": "kgraves/ctci", "max_issues_repo_issues_event_min_datetime": "2016-11-03T00:32:52.000Z", "max_issues_repo_issues_event_max_datetime": "2018-04-14T21:57:47.000Z", "max_forks_repo_path": "edition4/js/ch04/4-6.js", "max_forks_repo_name": "kgraves/ctci", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": null, "max_issues_count": 2, "max_forks_count": null, "avg_line_length": 23.7096774194, "max_line_length": 73, "alphanum_fraction": 0.6387755102}
function Node(value, left, right) {
  this.value = value;
  this.left = left;
  this.right = right;
}

function isInSubtree(root, value) {
  // base cases
  if (!root) return false;
  if (root.value === value) return true;

  return isInSubtree(root.left, value) || isInSubtree(root.right, value);
}

/**
 * Find the fist common ancestor shared between v1, and v2.
 *
 * This algorithm assumes that both values exist in the given tree.
 */
function firstCommonAncestor(root, v1, v2) {
  if (isInSubtree(root.left, v1) && isInSubtree(root.left, v2)) {
    return firstCommonAncestor(root.left, v1, v2);
  }
  if (isInSubtree(root.right, v1) && isInSubtree(root.right, v2)) {
    return firstCommonAncestor(root.right, v1, v2);
  }

  // if v1 and v2 are not found on one side of root,
  // then root must straddle both values.
  return root.value;
}

// tests
var assert = require('assert');

describe('firstCommonAncestor', function() {
  var root = null;

  before(function() {
    // create binary tree
    var five = new Node(
      5,
      new Node(4),
      new Node(3)
    );
    var eight = new Node(
      8,
      new Node(6),
      null
    );
    root = new Node(1, five, eight);
  });

  it('should find the values', function() {
    assert.equal(firstCommonAncestor(root, 4, 3), 5);
    assert.equal(firstCommonAncestor(root, 4, 6), 1);
    assert.equal(firstCommonAncestor(root, 4, 8), 1);
    assert.equal(firstCommonAncestor(root, 6, 8), 8);
  });

});
