Count Tree Nodes Greater Than Every Cross-Subtree Pair Sum and Product
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Given a binary tree of integers, count the nodes whose value is larger than every sum and every product that can be formed by taking one value from the node's left subtree and one value from its right subtree. The comparison uses the node's entire left and right subtrees, not only its direct children.
The candidate's report describes the test only as comparing the sum and the product of one value from each subtree with the node's value; this version fixes the exact rule in Rules below.
### Function Signature
```python
def count_dominant_nodes(tree: list[int | None]) -> int:
```
### Rules
- `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`.
- For a node with value `v`, let `L` be the values in its entire left subtree and `R` the values in its entire right subtree.
- The node is counted when both `L` and `R` are nonempty and, for every pair with `a` taken from `L` and `b` taken from `R`, both `a + b < v` and `a * b < v` hold. Both inequalities are strict.
- A node whose left subtree or right subtree is empty, including every leaf, is never counted.
- Return the number of counted nodes as a single integer.
### Constraints
- `1 <= number of nodes <= 10^4`
- `-10^4 <= node value <= 10^4`; values may be negative, zero or repeated.
- Every sum and product of two node values lies within `[-10^8, 10^8]`.
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
### Examples
**Example 1**
```text
Input: tree = [8, 3, 4, 1, 1]
Output: 1
```
```text
8
/ \
3 4
/ \
1 1
```
Node 3 has `L = {1}` and `R = {1}`: `1 + 1 = 2 < 3` and `1 * 1 = 1 < 3`, so it is counted. For the root, `L = {3, 1, 1}` and `R = {4}`; every sum is at most `3 + 4 = 7 < 8`, but the product `3 * 4 = 12` is not less than 8, so the root is not counted. Node 4 and the two leaves have an empty subtree.
**Example 2**
```text
Input: tree = [5, -3, -2]
Output: 0
```
The root's only pair is `(-3, -2)`: the sum `-5` is less than 5, but the product `6` is not. The two children are leaves.
**Example 3**
```text
Input: tree = [20, -6, 3, -7, 1, None, 2]
Output: 1
```
```text
20
/ \
-6 3
/ \ \
-7 1 2
```
For the root, `L = {-6, -7, 1}` and `R = {3, 2}`. The largest pair sum is `1 + 3 = 4` and the largest pair product is `1 * 3 = 3`, both below 20, so the root is counted. Node -6 has the single pair `(-7, 1)`, whose sum `-6` is not strictly less than `-6`, so it is not counted. Node 3 has no left subtree, and the remaining nodes are leaves.
Overview: Count the nodes of a binary tree whose value is strictly greater than every sum and every product formed by one value from the node's whole left subtree and one from its whole right subtree. It tests tree recursion, summarizing subtrees in one pass, products of negative numbers, and edge cases such as leaves and one-sided nodes.
Read the full Google Software Engineer interview experience this question came from
Given a binary tree of integers, count the nodes whose value is larger than every sum and every product that can be formed by taking one value from the node's left subtree and one value from its right subtree. The comparison uses the node's entire left and right subtrees, not only its direct children.
**Input**
- `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child (`null` in JavaScript and Java, an empty `std::optional<int>` in C++); a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`.
**Rules**
- For a node with value `v`, let `L` be the values in its entire left subtree and `R` the values in its entire right subtree.
- The node is counted when both `L` and `R` are nonempty and, for every pair with `a` taken from `L` and `b` taken from `R`, both `a + b < v` and `a * b < v` hold. Both inequalities are strict.
- A node whose left subtree or right subtree is empty, including every leaf, is never counted.
- Return the number of counted nodes as a single integer.
**Constraints**
- `1 <= number of nodes <= 10^4`
- `-10^4 <= node value <= 10^4`; values may be negative, zero or repeated.
- Every sum and product of two node values lies within `[-10^8, 10^8]`.
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
No node value, pair sum, pair product or answer can exceed 2^31 - 1 in absolute value, so 32-bit integers suffice in every language.
**Example 1**
```
Input: tree = [8, 3, 4, 1, 1]
Output: 1
```
```
8
/ \
3 4
/ \
1 1
```
Node 3 has `L = {1}` and `R = {1}`: `1 + 1 = 2 < 3` and `1 * 1 = 1 < 3`, so it is counted. For the root, `L = {3, 1, 1}` and `R = {4}`; every sum is at most `3 + 4 = 7 < 8`, but the product `3 * 4 = 12` is not less than 8, so the root is not counted. Node 4 and the two leaves have an empty subtree.
**Example 2**
```
Input: tree = [20, -6, 3, -7, 1, None, 2]
Output: 1
```
```
20
/ \
-6 3
/ \ \
-7 1 2
```
For the root, `L = {-6, -7, 1}` and `R = {3, 2}`. The largest pair sum is `1 + 3 = 4` and the largest pair product is `1 * 3 = 3`, both below 20, so the root is counted. Node -6 has the single pair `(-7, 1)`, whose sum `-6` is not strictly less than `-6`, so it is not counted. Node 3 has no left subtree, and the remaining nodes are leaves.
Constraints
- tree is a level-order listing with None for a missing child; a missing node has no child slots, trailing None entries may be omitted, and tree[0] is never None.
- 1 <= number of nodes <= 10^4
- -10^4 <= node value <= 10^4; values may be negative, zero or repeated.
- Every sum and product of two node values lies within [-10^8, 10^8].
- The tree is not necessarily balanced; its height can be as large as the number of nodes.
Examples
Input: ([5],)
Expected Output: 0
Explanation: Minimum valid: a lone root is a leaf, so nothing is counted.
Input: ([8, 3, 4, 1, 1],)
Expected Output: 1
Explanation: Source example 1: node 3 counts (2 < 3, 1 < 3); the root fails because 3 * 4 = 12 is not below 8.
Hints
- A node with an empty left or right subtree, including every leaf, is never counted, so only nodes with two children can contribute.
- Both inequalities are strict and must hold for every cross pair; two negative values multiply to a positive product.
- The tree can be a single chain of up to 10^4 nodes, so consider how deep your traversal goes.