Find the deepest shared ancestor of two keys in a binary search tree
Company: Amazon
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given a binary search tree in level-order form and two distinct keys present in it, return the key of their lowest common ancestor, where a node counts as its own ancestor. Tests reasoning with the search tree ordering, plus time and space analysis on skewed trees.
Read the full Amazon Frontend Engineer interview experience this question came from
