Interview Question for Software Engineer at Google:

This one is covered a lot on the web and in technical books, but every one I've seen assumes it's a binary search tree. Here he didn't want me to assume it was a binary search tree.

I think I would go with a modified dfs which terminates early. I would need a global variable to indicate the closest ancestor;

//return 0 - none found, 1 - a found, 2 - b found, 3 - both found
public int modifiedDFS(Node node, Node a, Node b, int ) {
    int res=0;
    if (node) {
        if ((node.left == a) || (node.right == a)) {
            res += 1;
        }

        if ((node.left == b) || (node.right == b)) {
            res += 2;
        }

        if (res == 3) {
            lowest = node;
        } else {
            int l = modifiedDFS(node.right, a, b);
            int r = modifiedDFS(node.left, a, b);

            if ((l==3) || (r==3)) {
                //lower node is the one
                res = 3;
            } else {
                if ((3 == (l+r)) ||
                    (3 == (l+res)) ||
                    (3 == (r+res)) {
                    //i am the lowest
                    lowest = node;
                    res = 3;
                } else {
                    if ((l==1)||(r==1))
                        res = 1;
                    if ((2==l)||(2==r))
                        res = 2;
                }
            }
        }
    }
    return res;
}

That may or may not work (I didn't trace through the code), but there's a much simpler and faster way to do it. Worst-case running time is O(lg n). With yours, worst-case running time is O(n).

Remember: you're given a pointer to the nodes in question. To traverse from a leaf node to the root is worst-case O(lg n) operations. Think of something you could do to take advantage of that.