> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/236.-lowest-common-ancestor-of-a-binary-tree.md).

# 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

```java
// 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;
}

```