Lowest Common Ancestor of a Binary Tree

Find the lowest common ancestor of the nodes with values p and q in an ordinary binary tree (not a BST — values are in no particular order). The LCA is the deepest node that has both as descendants; a node is a descendant of itself.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input:

• line 1: the tree (distinct values)
• line 2: p q — both values are in the tree (they may be equal)

Output: the value of the LCA.

Constraints: 2 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: recurse: return the node if it is p or q; otherwise ask both subtrees. If both sides found something, the current node is the LCA; if only one did, pass that result up.