#ctci

FirstCommonAncestor.java

// First of all, we need to know if the nodes p and q both exist in the tree
// if not, then return null.

// if yes, we need to figure out which side they are in.
// if they are in the same side, then we go to that side to find the ancestor (in this way, we eliminate half the tree)
// otherwise, we have found the first common ancestor.
public class FirstCommonAncestor{
    public Node findAncestor(Node root, Node p, Node q){
        // first of all, we need to know if p and q actually exist in the tree
        // if either is not in the tree, then we should return null
        
        if(!covered(root, p) || !covered(root, q)) return null;
        
        return find(root, p, q);
    }
    
    private boolean covered(Node root, Node target){
        if(root == null) return false;
        
        if(root == target) return true;
        
        return covered(root.left, target) || covered(root.right, target);
    }
    
    private Node find(Node root, Node p, Node q){
        if(root == null) return null;
        if(root == p || root == q) return root;
        
        // let's check if they are in the same subtree
        boolean p_is_in_left = covered(root.left, p);
        boolean q_is_in_left = covered(root.left, q);
        
        // if not, then we have found the first common ancestor root
        if(p_is_in_left != q_is_in_left) return root; 
        
        Node side = p_is_in_left ? root.left : root.right;
        return find(side, p, q);
    }
}