Find the deepest shared ancestor of two keys in a binary search tree

Given a binary search tree and two distinct keys p and q that are both in the tree, return the key of their lowest common ancestor: the node farthest from the root whose subtree contains both p and q. A node's subtree includes the node itself, so if one of the two keys is an ancestor of the other, that key is the answer.

Function Signature

def lowest_common_ancestor(root: list[int | None], p: int, q: int) -> int:

Rules

• The tree is given in level order. The first element is the root. Then, for each non-null node in the order it appears, the list gives its left child followed by its right child, with None for a missing child. Trailing None values may be omitted.
• All keys are distinct. For every node, every key in its left subtree is smaller than the node's key, and every key in its right subtree is larger.
• The common ancestors of p and q all lie on one path from the root, so exactly one of them is farthest from the root. Return its key.

Constraints

• The tree has between 2 and 100000 nodes.
• -10^9 <= key <= 10^9 for every key
• p != q, and both p and q are keys in the tree.
• The tree is not necessarily balanced; its height can equal the number of nodes.

Examples

Example 1

Input:  root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 12, q = 5
Output: 10

The root 20 has children 10 and 30. Node 10 has children 5 and 15, node 30 has children 25 and 40, and node 15 has children 12 and 18. Key 5 is in the left subtree of 10 and key 12 is in its right subtree, so 10 is the deepest node above both.

Example 2

Input:  root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 15, q = 12
Output: 15

Node 15 is the parent of 12, and a node counts as part of its own subtree.

Example 3

Input:  root = [20, 10, 30, 5, 15, 25, 40, None, None, 12, 18], p = 18, q = 25
Output: 20

Key 18 is in the root's left subtree and key 25 is in its right subtree, so only the root contains both.

Lowest Common Ancestor in a Level-Order Binary Search Tree

Hints

1. Only non-null nodes contribute child slots in the level-order list, so a node's children are not always at positions 2i+1 and 2i+2.
2. From a node's key alone, the BST ordering tells you which side of that node each of p and q lies on. Remember that a node counts as part of its own subtree.
3. The tree can be a single chain of 100000 nodes, so do not rely on the tree being balanced or on deep recursion.

Approach

Decode the list, then walk down from the root.

Decoding: keep a pointer nxt to the next unread slot, starting at index 1. Visit the list in order, and for every non-null entry consume up to two slots from nxt as its left and right child. A None slot means no child, and a slot past the end of the list is an omitted trailing None. Non-null entries appear in breadth-first order, so this reproduces the encoding exactly. A fixed 2i+1 / 2i+2 formula does not, because missing nodes have no child slots.

Walk: let lo = min(p, q) and hi = max(p, q). At the current node, if hi is smaller than its key, both keys are in the left subtree, so move left. If lo is larger than its key, both are in the right subtree, so move right. Otherwise stop and return the current key.

Invariant: the current node's subtree contains both p and q. It holds at the root, and each move keeps it because the BST ordering puts every key smaller than a node in its left subtree and every larger key in its right subtree. When the walk stops, either lo < key < hi, so p and q lie in different child subtrees and no child contains both, or the key equals p or q, so no proper descendant contains that key. Either way the current node is the deepest node whose subtree holds both keys, which the statement guarantees is unique.

Edge cases: the answer may be p or q itself, including the root; argument order does not matter because of min/max; omitted trailing None values are handled by the bounds check on nxt; the tree may be a single chain of 100000 nodes, so both phases are iterative rather than recursive; keys are compared directly rather than subtracted, because the difference of two keys can reach 2 * 10^9 and overflow a 32-bit int.

• Time complexity: O(n)
• Space complexity: O(n)