1. Depth First Search

Intuition

The lowest common ancestor (LCA) is the deepest node that has both p and q as descendants. We traverse the tree and track whether each subtree contains p, q, or both. The first node where we find both targets in its subtree (including itself) is the LCA. Once found, we can stop searching.

Algorithm

1. Define dfs(node) that returns a pair of booleans indicating whether p and q are found in the subtree rooted at node.
2. If node is null or LCA is already found, return [false, false].
3. Recursively search left and right subtrees.
4. Combine results: foundP = left[0] or right[0] or (node == p) and similarly for foundQ.
5. If both foundP and foundQ are true and LCA is not yet set, mark the current node as LCA.
6. Return the combined result.
7. Call dfs(root) and return the LCA.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        lca = None

        def dfs(node):
            nonlocal lca
            if not node:
                return [False, False]
            if lca:
                return [False, False]

            left = dfs(node.left)
            right = dfs(node.right)
            res = [left[0] or right[0] or (node == p), left[1] or right[1] or (node == q)]
            if res[0] and res[1] and not lca:
                lca = node

            return res 

        dfs(root)
        return lca

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Depth First Search (Optimal)

Intuition

We can simplify the approach by returning the node itself rather than boolean flags. If a node is p or q, we return it immediately. Otherwise, we recursively search both subtrees. If both return non-null values, the current node must be the LCA. If only one side returns a value, we propagate that up since both targets are in that subtree.

Algorithm

1. If root is null, return null.
2. If root equals p or q, return root.
3. Recursively call on the left and right children.
4. If both left and right return non-null, return root (it's the LCA).
5. Otherwise, return whichever side is non-null (or null if both are null).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(
        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
    ) -> 'TreeNode':
        if root is None or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Breadth First Search

Intuition

Instead of recursion, we can use BFS to build a parent pointer map for each node. Once we have parent pointers, we trace the path from p to the root and store all ancestors. Then we trace from q upward until we hit a node that's already in p's ancestor set. That node is the LCA.

Algorithm

1. Use BFS to traverse the tree, storing each node's parent in a hash map.
2. Continue BFS until both p and q are found in the parent map.
3. Create an ancestors set and trace from p to the root, adding each node to the set.
4. Trace from q upward until finding a node that exists in the ancestors set.
5. Return that node as the LCA.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(
        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
    ) -> 'TreeNode':
        parent = {root: None}
        queue = deque([root])
        while p not in parent or q not in parent:
            node = queue.popleft()
            if node.left:
                parent[node.left] = node
                queue.append(node.left)
            if node.right:
                parent[node.right] = node
                queue.append(node.right)

        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]

        while q not in ancestors:
            q = parent[q]

        return q

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Returning Early Without Checking Both Subtrees

A common mistake in the recursive approach is returning as soon as you find p or q, without considering that the other target might be in a different subtree. The correct approach returns the current node if it matches a target, but the parent call must still check both subtree results to determine if the current node is the LCA.

Confusing Node Reference with Node Value

The problem asks for the LCA of specific nodes p and q, not nodes with values p.val and q.val. Since tree nodes can have duplicate values, you must compare node references (node == p) rather than values (node.val == p.val). Using value comparison fails when multiple nodes share the same value.

Mishandling the Case Where One Node is Ancestor of the Other

When p is an ancestor of q (or vice versa), the LCA is the ancestor node itself. A common bug is failing to recognize this case and continuing to search unnecessarily. In the optimal recursive solution, returning the node immediately when it matches p or q naturally handles this case, since the other target will be found in that node's subtree.