Recursive DFS

The key observations:

• If the current node is null, return null.
• If the current node is p or q, return the current node immediately (it is the LCA if the other is a descendant, or we'll find the true LCA higher up).
• Recurse into both subtrees. If both return non-null, the current node is the LCA (p and q are in different subtrees).
• If only one side returns non-null, propagate that result upward.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; // If root is p or q, it is the LCA (or will propagate up) if (root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // p found in one subtree, q in the other — current node is LCA if (left != null && right != null) return root; // Both in same subtree — propagate the found node up return left != null ? left : right; }

Trace for Example 1 (p=5, q=1):

• At node 3: recurse left (returns 5) and right (returns 1) → both non-null → return 3 ✓
• At node 5: root == p → return 5 immediately
• At node 1: root == q → return 1 immediately

• Time: O(n) — visits each node at most once.
• Space: O(h) — recursion stack depth (O(log n) balanced, O(n) skewed).