Challenge – Find First Common Ancestor

Question:
               How would you find the first common ancestor of two nodes in a binary search tree? First as in the lowest in the tree. Another way to ask is to find the lowest common ancestor of two nodes.

 Meanwhile, check out the challenges from previous weeks here

Answer:

TreeNode findFirstCommonAncestor(TreeNode root, TreeNode p,
 TreeNode q) {

    if (root == null) {
        return null;
    }

    if (root == p || root == q) {
 return root;
    }

    TreeNode left = findFirstCommonAncestor(root.left, p, q);
    TreeNode right = findFirstCommonAncestor(root.right, p, q);

    if ((left == p && right == q) ||
        (left == q && right == q)) {
 return root;
    }

    return (left != null) ? left : right;
} 

Alternate:

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {

    if (root == null) {
        return null;
    }

    if (root.value == p || root.value == q) {
 return root;
    }

    if (root.value > p && root.value > q ) {
        return findFirstCommonAncestor(root.left, p, q);
    }
    else if (root.value < p && root.value < q ) {
        return findFirstCommonAncestor(root.right, p, q);
    }
    else {
        return root;
    }
}