Nearest Shared Manager

medium

An org directory is stored as a binary search tree keyed by employee ID: every ID in a node's left subtree is smaller, every ID in its right subtree is larger. Two employees filed a joint request, and it must be approved by their nearest shared manager — the deepest node that has both of them in its subtree. (A node counts as its own ancestor, so a manager can approve a request involving themselves.)

Given the BST's level-order values and two IDs p and q that both exist in the tree, return the value of their lowest common ancestor.

Tests pass a level-order array plus the two IDs; implement the core in _lca on real nodes and return the LCA node.

Example 1

in values = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8

out 6

2 sits left of 6 and 8 sits right of 6 — the split point is the LCA.

Example 2

in values = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4

out 2

4 lives inside 2's subtree, so 2 is its own ancestor and the answer.

Example 3

in values = [2, 1], p = 1, q = 2

out 2

Constraints

· 2 <= number of nodes <= 10^5
· all node values are distinct
· p != q, and both exist in the tree
· the tree is a valid BST