216. Lowest Common Ancestor of a Binary Tree
You receive the root of a binary tree — no ordering guarantees this time — together with two of its nodes, p and q. Return their lowest common ancestor: the deepest node whose subtree contains both of them.
A node is considered part of its own subtree, so when q hangs somewhere below p, the correct answer is p.
The judge finds p and q by value (all values in the tree are distinct, and both are guaranteed to exist) and passes your function the actual TreeNode objects; return the ancestor node, and its value gets printed.
Unlike the BST variant, a comparison tells you nothing about where a node hides — you have to discover both locations yourself, ideally in one traversal.
Example 1:
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
Explanation: 5 sits in the root's left subtree and 1 in its right subtree, so the only node containing both is the root, 3.
Example 2:
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: 4 is a descendant of 5, and a node belongs to its own subtree — so the deepest node containing both is 5 itself.
Constraints:
- 2 ≤ number of nodes ≤ 10⁵
- -10⁹ ≤ node value ≤ 10⁹, and all values are distinct
- p ≠ q, and both values exist in the tree
Hints:
If every node carried a parent pointer you could just walk upward. Nothing stops you from manufacturing that: one traversal fills a child → parent map, then collect all of p's ancestors into a set and climb from q until you hit one.
One recursion answers it in a single pass. Define the call to return: the node itself if it is p or q, else whatever its children's calls surface. If both the left and right calls come back non-null, the current node is where the two were first united — that is the LCA. Otherwise forward the one non-null result upward.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Expected output: 3