Lowest Common Ancestor of Two Values in a Binary Tree Given in Level Order
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a binary tree whose node values are all distinct, and two values `p` and `q` that both occur in it, return the value of their lowest common ancestor: the deepest node that has both the node with value `p` and the node with value `q` in its subtree. A node counts as part of its own subtree, so a node can be its own ancestor.
### Function Signature
```python
def lowest_common_ancestor(tree: list[int | None], p: int, q: int) -> int:
```
### Rules
- **Input format.** `tree` is the level-order serialization of the tree. `tree[0]` is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. `None` marks a missing child, children of missing nodes are not listed, and trailing `None` entries may be omitted.
- If the node with value `p` is an ancestor of the node with value `q`, the answer is `p` (and symmetrically for `q`).
- Return the ancestor's value; values are distinct, so the answer is unique.
### Constraints
- `2 <= number of nodes <= 100000`
- `-10^9 <= node value <= 10^9`, and all values are distinct.
- `p != q`, and both `p` and `q` occur in the tree.
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
### Examples
**Example 1**
Input: `tree = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]`, `p = 5`, `q = 1`
Output: `3`
Explanation: 5 is the root's left child and 1 is the root's right child, so the deepest node containing both is the root.
**Example 2**
Input: `tree = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]`, `p = 5`, `q = 4`
Output: `5`
Explanation: 4 lies in the subtree of 5 (5 to 2 to 4), and a node is part of its own subtree.
**Example 3**
Input: `tree = [1, 2]`, `p = 1`, `q = 2`
Output: `1`
Overview: Given a binary tree in level-order form with distinct values, find the deepest node that has both of two given values in its subtree, where a node counts as part of its own subtree. Trees can hold 100,000 nodes and be completely unbalanced, so the task tests tree traversal and awareness of recursion depth.