236. Lowest Common Ancestor of a Binary Tree

Intuition

To find the Lowest Common Ancestor (LCA) of two nodes in a binary tree, we traverse the tree from the root, looking for both nodes. The first node in the traversal where both nodes are found in separate subtrees (or one is the current node and the other in a subtree) is the LCA. This works because we go bottom-up, ensuring the "lowest" common node is selected.

Complexity

Space Complexity	Time Complexity
$\text{O}(`)$	$O(N)$

Code

// Global variable to store the result
TreeNode lowestCommonAncestorNode = null;

// Helper function to find LCA
public boolean findLCA(TreeNode currentNode, TreeNode nodeP, TreeNode nodeQ) {
    // Base case: return false if the node is null
    if (currentNode == null) return false;

    // Check if current node is either nodeP or nodeQ
    boolean isCurrentNodeTarget = (currentNode == nodeP) || (currentNode == nodeQ);

    // Recurse on left and right subtrees
    boolean foundInLeftSubtree = findLCA(currentNode.left, nodeP, nodeQ);
    boolean foundInRightSubtree = findLCA(currentNode.right, nodeP, nodeQ);

    // If any two of the three flags are true, we've found the LCA
    if ((foundInLeftSubtree && foundInRightSubtree) || 
        (isCurrentNodeTarget && foundInLeftSubtree) || 
        (isCurrentNodeTarget && foundInRightSubtree)) {
        
        lowestCommonAncestorNode = currentNode;
        
        // Prevent propagating further since LCA is already found
        return false;
    }

    // Return true if this node or its subtree contains one of the targets
    return isCurrentNodeTarget || foundInLeftSubtree || foundInRightSubtree;
}

// Public method to call the helper and return the result
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode nodeP, TreeNode nodeQ) {
    findLCA(root, nodeP, nodeQ);
    return lowestCommonAncestorNode;
}