Lowest Common Ancestor of a BST

In a binary search tree, find the lowest common ancestor (LCA) of the nodes with values p and q: the deepest node that has both of them as descendants. A node counts as 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 BST (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: use the BST order. If both values are smaller than the current node, the LCA is in the left subtree; if both are larger, in the right; otherwise the current node splits them — it is the answer. O(height), no recursion needed.