CTCI 4.7

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid sorting additional nodes in a data structure. NODE: This is not necessarily a binary search tree.

CTCI 4.7.java

public static Node findCommonAncestor(Node root, Node first, Node second){
    Result r = findCommonAncestorHelper(root, first, second);
    if(r.state == 2) return r.cross;
    else return null;
}

public static Result findCommonAncestorHelper(Node thisNode, Node n, Node m){
    if(thisNode == null) return Result(null, 0);
    
    Result leftResult = findCommonAncestor(thisNode.left, n, m);
    if(leftResult.state == 2) return leftResult;
    Result rightResult = findCommonAncestor(thisNode.right, n, m);
    if(rightResult.state == 2) return rightResult;
    
    int state = leftResult.state + rightResult.state;
    if(thisNode == n && thisNode == m) state += 2;
    else if(thisNode == n || thisNode == m) state++;
    
    Result result = new Result(null, state);
    if(state == 2) result.cross = thisNode;
    
    return result;
}

class Result{
    Node cross;
    int state;
    retult(Node n, int i){
        cross = n;
        state = i;
    }
}