Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Trees - Understanding tree node structure and parent-child relationships
- Depth First Search (DFS) - Recursive tree traversal to explore all nodes and combine subtree results
- Breadth First Search (BFS) - Level-order traversal using a queue to build parent pointers
- Hash Maps - Storing parent references for each node to trace paths back to the root
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
- Define
dfs(node)that returns a pair of booleans indicating whetherpandqare found in the subtree rooted atnode. - If
nodeisnullor LCA is already found, return[false, false]. - Recursively search left and right subtrees.
- Combine results:
foundP = left[0] or right[0] or (node == p)and similarly forfoundQ. - If both
foundPandfoundQaretrueand LCA is not yet set, mark the current node as LCA. - Return the combined result.
- 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 lcaTime & Space Complexity
- Time complexity:
- Space complexity:
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
- If
rootisnull, returnnull. - If
rootequalsporq, returnroot. - Recursively call on the
leftandrightchildren. - If both
leftandrightreturn non-null, returnroot(it's the LCA). - Otherwise, return whichever side is non-
null(ornullif both arenull).
# 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 rightTime & Space Complexity
- Time complexity:
- Space complexity:
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
- Use BFS to traverse the tree, storing each node's parent in a hash map.
- Continue BFS until both
pandqare found in theparentmap. - Create an
ancestorsset and trace frompto the root, adding each node to the set. - Trace from
qupward until finding a node that exists in theancestorsset. - 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 qTime & Space Complexity
- Time complexity:
- Space complexity:
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.