Lowest Common Ancestor
The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the deepest node that is an ancestor of both. It is a fundamental tree problem with applications in network routing, version control (merge-base), and compiler design.
Summary of Approaches
| Approach | Tree Type | Time | Space | Notes |
|---|---|---|---|---|
| Path comparison | Binary Tree | O(n) | O(n) | Simple, two traversals |
| Single traversal | Binary Tree | O(n) | O(h) | One pass, recursive |
| BST traversal | BST | O(h) | O(1) | Exploits ordering |
| Parent pointers | Any | O(h) | O(h) | Iterative, if parent links exist |
Where h = tree height (O(log n) for balanced, O(n) worst case).
Method 1: Path Comparison (Binary Tree)
Find path from root to each node, then compare the paths.
- Find path from root to
n1, store in arraypath1 - Find path from root to
n2, store in arraypath2 - Walk both arrays together — the last element where they agree is the LCA
Time: O(n) — two traversals + linear scan
Space: O(n) — two path arrays
def find_path(root, path, k):
if root is None:
return False
path.append(root.val)
if root.val == k:
return True
if find_path(root.left, path, k) or find_path(root.right, path, k):
return True
path.pop()
return False
def lca_path(root, n1, n2):
path1, path2 = [], []
if not find_path(root, path1, n1) or not find_path(root, path2, n2):
return None # one or both nodes not present
for i in range(min(len(path1), len(path2))):
if path1[i] != path2[i]:
return path1[i - 1]
return path1[min(len(path1), len(path2)) - 1]
Method 2: Single Traversal (Binary Tree)
One recursive pass — O(n) time, O(h) space. This is the standard interview solution.
Intuition: If the current node is n1 or n2, it could be the LCA. Recurse into both subtrees. If both sides return non-null, the current node is the LCA (one target is in each subtree).
def lca(root, p, q):
if root is None:
return None
if root.val == p or root.val == q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root # p in one subtree, q in the other
return left if left else right
Node* findLCA(Node* root, int n1, int n2) {
if (root == nullptr) return nullptr;
if (root->key == n1 || root->key == n2) return root;
Node* left_lca = findLCA(root->left, n1, n2);
Node* right_lca = findLCA(root->right, n1, n2);
if (left_lca && right_lca) return root;
return left_lca ? left_lca : right_lca;
}
Note: This assumes both nodes are present. If one is absent, it returns the present node as LCA rather than
null. Pass boolean flagsfound1/found2to handle this correctly.
Method 3: LCA in a Binary Search Tree (BST)
A BST's ordering lets us find the LCA in O(h) time without a full traversal.
Algorithm: Starting from the root:
- Both
pandq< root → LCA is in the left subtree - Both > root → LCA is in the right subtree
- Otherwise → root is the LCA (paths to
pandqdiverge here)
def lca_bst(root, p, q):
while root:
if p < root.val and q < root.val:
root = root.left
elif p > root.val and q > root.val:
root = root.right
else:
return root # divergence point = LCA
return None
func lcaBST(root *TreeNode, p, q int) *TreeNode {
for root != nil {
if p < root.Val && q < root.Val {
root = root.Left
} else if p > root.Val && q > root.Val {
root = root.Right
} else {
return root
}
}
return nil
}
Time: O(h) — O(log n) balanced, O(n) worst (skewed tree)
Space: O(1) iterative
Method 4: Using Parent Pointers
If nodes have parent pointers (common in OS process trees, DOM), use a depth-leveling approach similar to finding the intersection of two linked lists.
def lca_with_parents(p, q):
def depth(node):
d = 0
while node.parent:
node, d = node.parent, d + 1
return d
dp, dq = depth(p), depth(q)
while dp > dq:
p, dp = p.parent, dp - 1
while dq > dp:
q, dq = q.parent, dq - 1
while p != q:
p, q = p.parent, q.parent
return p
Time: O(h) Space: O(1)
Edge Cases (LeetCode #236)
| Case | Result |
|---|---|
p is ancestor of q |
Returns p |
q is ancestor of p |
Returns q |
| Neither is ancestor of the other | Returns the split node |
| One node missing (Method 2) | Returns the present node (use flags for strict correctness) |

