Binary Search Tree Scenario

Leverage the ordering property where left descendants contain smaller values than their parent, while right descendants contain larger values. Starting from the root, compare target node values with the current node to determine the traversal direction.

Recursive impplementation:

public TreeNode findAncestor(TreeNode current, TreeNode nodeX, TreeNode nodeY) {
    if (current == null) return null;
    
    int larger = Math.max(nodeX.val, nodeY.val);
    int smaller = Math.min(nodeX.val, nodeY.val);
    
    if (current.val > larger) {
        return findAncestor(current.left, nodeX, nodeY);
    } else if (current.val < smaller) {
        return findAncestor(current.right, nodeX, nodeY);
    }
    return current;
}

Iterative approach:

public TreeNode findAncestorIterative(TreeNode current, TreeNode nodeX, TreeNode nodeY) {
    while (current != null) {
        int larger = Math.max(nodeX.val, nodeY.val);
        int smaller = Math.min(nodeX.val, nodeY.val);
        
        if (current.val > larger) {
            current = current.left;
        } else if (current.val < smaller) {
            current = current.right;
        } else {
            break;
        }
    }
    return current;
}

Trees with Parent References

When nodes maintain parent pointers, transform the problem into finding the intersection of two linked lists. Each path from a node to the root forms a reverse-linked list structure.

Calculate depths to align starting positions, then advance both pointers until convergence:

class NodeWithParent {
    NodeWithParent parent, left, right;
}

public NodeWithParent findCommonAncestor(NodeWithParent root, 
                                         NodeWithParent alpha, 
                                         NodeWithParent beta) {
    int depthAlpha = calculateDepth(alpha);
    int depthBeta = calculateDepth(beta);
    
    NodeWithParent deeper = (depthAlpha > depthBeta) ? alpha : beta;
    NodeWithParent shallower = (depthAlpha > depthBeta) ? beta : alpha;
    int difference = Math.abs(depthAlpha - depthBeta);
    
    while (difference-- > 0) {
        deeper = deeper.parent;
    }
    
    while (deeper != shallower) {
        deeper = deeper.parent;
        shallower = shallower.parent;
    }
    return deeper;
}

private int calculateDepth(NodeWithParent node) {
    int count = 0;
    while (node != null) {
        node = node.parent;
        count++;
    }
    return count;
}

Standard Binary Tree (Guaranteed Existence)

For general binary trees without parent references, employ post-order traversal. When targets appear in different subtrees of the current node, or one equals the current node, that node represents the lowest common ancestor.

public TreeNode locateAncestor(TreeNode current, TreeNode targetA, TreeNode targetB) {
    if (current == null || current == targetA || current == targetB) {
        return current;
    }
    
    TreeNode leftResult = locateAncestor(current.left, targetA, targetB);
    TreeNode rightResult = locateAncestor(current.right, targetA, targetB);
    
    if (leftResult != null && rightResult != null) {
        return current;
    }
    return (leftResult != null) ? leftResult : rightResult;
}

Standard Binary Tree with Existence Validation

When nodes might not exist in the tree, track existence flags during traversal to prevent false positives.

class SearchResult {
    boolean hasFirst, hasSecond;
    TreeNode ancestor;
    
    SearchResult(boolean first, boolean second, TreeNode node) {
        this.hasFirst = first;
        this.hasSecond = second;
        this.ancestor = node;
    }
}

public TreeNode verifyAndFind(TreeNode root, TreeNode first, TreeNode second) {
    SearchResult outcome = traverse(root, first, second);
    return (outcome.hasFirst && outcome.hasSecond) ? outcome.ancestor : null;
}

private SearchResult traverse(TreeNode current, TreeNode first, TreeNode second) {
    if (current == null) {
        return new SearchResult(false, false, null);
    }
    
    SearchResult leftData = traverse(current.left, first, second);
    SearchResult rightData = traverse(current.right, first, second);
    
    boolean foundFirst = leftData.hasFirst || rightData.hasFirst || current == first;
    boolean foundSecond = leftData.hasSecond || rightData.hasSecond || current == second;
    
    if (current == first || current == second) {
        return new SearchResult(foundFirst, foundSecond, current);
    }
    
    if (leftData.ancestor != null && rightData.ancestor != null) {
        return new SearchResult(foundFirst, foundSecond, current);
    }
    
    TreeNode validAncestor = (leftData.ancestor != null) ? leftData.ancestor : rightData.ancestor;
    return new SearchResult(foundFirst, foundSecond, validAncestor);
}

Alternative approach using explicit subtree coverage checks:

public TreeNode findWithValidation(TreeNode root, TreeNode alpha, TreeNode beta) {
    if (!existsInSubtree(root, alpha) || !existsInSubtree(root, beta)) {
        return null;
    }
    return findHelper(root, alpha, beta);
}

private boolean existsInSubtree(TreeNode current, TreeNode target) {
    if (current == null) return false;
    if (current == target) return true;
    return existsInSubtree(current.left, target) || existsInSubtree(current.right, target);
}

private TreeNode findHelper(TreeNode current, TreeNode alpha, TreeNode beta) {
    if (current == null || current == alpha || current == beta) return current;
    
    boolean alphaInLeft = existsInSubtree(current.left, alpha);
    boolean betaInLeft = existsInSubtree(current.left, beta);
    
    if (alphaInLeft != betaInLeft) return current;
    
    TreeNode nextBranch = alphaInLeft ? current.left : current.right;
    return findHelper(nextBranch, alpha, beta);
}