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.
You are given a binary tree whose node values are all distinct, together with two values `p` and `q` that both occur in the tree. Return the value of their lowest common ancestor: the deepest node whose subtree contains both the node with value `p` and the node with value `q`. A node counts as part of its own subtree, so a node can be its own ancestor: if the node with value `p` is an ancestor of the node with value `q`, the answer is `p` (and symmetrically for `q`). Because values are distinct, the answer is unique.
**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. A missing entry is `None` in Python, `null` in JavaScript, a `null` element of the `java.util.List<Integer>` in Java, and `std::nullopt` in C++.
Return the value of the lowest common ancestor as an integer. Every value (the tree entries, `p`, `q` and the answer) lies in [-10^9, 10^9], so no value exceeds 2^31 - 1 and a signed 32-bit integer suffices in every language.
**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.
**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.
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
Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 5, 1)
Expected Output: 3
Explanation: Source Example 1: p and q are the root's two children, so the root is the answer.
Input: ([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], 5, 4)
Expected Output: 5
Explanation: Source Example 2: 4 lies under 5 (5 -> 2 -> 4), so p is its own ancestor and is returned.
Hints
- Before reasoning about ancestors, make sure you can tell which node owns each entry of the list: entries are handed out two at a time, in order, only to nodes that actually exist.
- A node counts as its own ancestor, so when one of the two values sits inside the other's subtree, the answer is the upper one.
- The tree can be a single chain as deep as the number of nodes, so prefer an approach whose depth of work does not depend on call-stack recursion.