Find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.

commonAncestor

function covers(root, node){
    if (root === null ) return false;
    if (root === node ) return true;
    return covers(root.left, node) || covers(root.right, node);
}

function commonAncestorHelper(root, node1, node2){
    if (root === null ) return false;
    if (root === node1 || root === node2 ) return root;
    
    var isOnLeft1 = covers(root.left, node1);
    var isOnLeft2 = covers(root.left, node2);
    
    // if node1 and node2 are on different side
    if (isOnLeft1 !== isOnLeft2) return root;

    if (isOnLeft1 && isOnLeft2){
        return commonAncestorHelper(root.left, node1, node2);
    } else{
        return commonAncestorHelper(root.right, node1, node2);
    }
}

function commonAncestor(root, node1, node2){
    if ( !covers(root, node1) || !covers(root, node2) ){
        return null;
    }
    return commonAncestorHelper(root, node1, node2);
}

// var a = {val: 1, left: null, right: null};
// var b = {val: 2, left: null, right: null};
// var c = {val: 3, left: null, right: null};
// var d = {val: 4, left: null, right: null};
// var e = {val: 5, left: null, right: null};
// var f = {val: 6, left: null, right: null};
// var g = {val: 7, left: null, right: null};
// var h = {val: 8, left: null, right: null};
// var i = {val: 9, left: null, right: null};
// var j = {val: 10, left: null, right: null};

// a.left = b;
// b.left = c;
// c.left = d;
// d.left = e;
// d.right = f;
// f.left = g;
// g.left = h;
// h.left = i;
// i.left = j;

// console.log(commonAncestor(c, e, f));