Lowest Common Ancestor Interview Questions

Optimal (general tree): If current node is p or q, return it. Recurse left and right. If both sides return non-null, current is LCA; else return the non-null side. Complexity: Time O(n) , Space O(height)

Optimal (BST): Walk from root — both smaller go left, both larger go right, otherwise current node is the split point. Complexity: Time O(height)

In a BST I can walk from the root: if both nodes are less, go left; both greater, go right; otherwise this node is the split and the LCA. That is O(h) and I do not need parent pointers. In a general binary tree I DFS and return a node if I found p or q in that subtree. If both sides return non-null, I am the LCA. I would not search BST with the general method first — they want the property.

I would not assume both p and q exist. I search, and if one is missing I must not return the other as LCA unless the problem says a node can be an ancestor of itself and both exist. LeetCode 236 assumes both exist. In a real interview I ask. Implementation: count found nodes or do an extra exists check. Silent wrong LCA is worse than a clarifying question.

I walk from p to root and store the path in a set, then walk from q until I hit the set. Or I compute depths and climb the deeper one, then climb together. Both are O(h) . Parent pointers make it like linked-list intersection. I would mention that analogy. If parents are missing I fall back to the DFS method.

Yes. I can reduce: LCA of a set is LCA(x, LCA of the rest). On a BST I still walk until the nodes are not all on one side. On a general tree I DFS and return when I have collected all targets in a subtree. I would ask whether the nodes are guaranteed to exist. This is a natural extension if I finished two-node LCA early.