Count Good Nodes in Binary Tree
Real-world version: Sensors With A Clear ViewThe statement here is our own: the same inputs, outputs and technique.
A survey network of altitude sensors is wired as a binary tree. tree is the level-order picture of the network. tree[0] is the root. After that the entries arrive in pairs: the next pair gives the left child and then the right child of the next node already read, and null marks a child that is not there. Pairs that would be all null at the end of the list may be left off. Each entry that is not null is the altitude of that sensor in metres, and altitudes may be negative.
Follow the links from the root down to a sensor. That sensor has a clear view when nothing on the way, counting the root and every sensor in between, stands strictly higher than it does. Return the number of sensors with a clear view.
Examples
Example 1
- Input
- tree = [4, 4, 2, null, 3, 1, 5]
- Output
- 3
The root sits at 4 and has a clear view. Its left child also sits at 4, and nothing on the way to it is above 4, so it counts. Its right child at 2 does not, nor does the sensor at 3 below the left child, nor the sensor at 1. The sensor at 5 has only 4 and 2 above it, so it counts. That makes 3.
Example 2
- Input
- tree = [-5, -6, -4]
- Output
- 2
The root at -5 counts. Its left child at -6 has the root above it at -5, which is higher, so it does not count. Its right child at -4 has only -5 above it, so it counts. That makes 2.
Example 3
- Input
- tree = [9, 3, 4, null, 5]
- Output
- 1
Only the root at 9 counts. The sensors at 3 and 4 sit below the root, and the sensor at 5, reached through the sensor at 3, still has the root at 9 on its path.
Constraints
- The number of sensors in the tree is in the range [1, 10^5].
- -10^4 <= tree[i] <= 10^4 for every entry that is not null.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def good_nodes(tree: list) -> int:public int goodNodes(Integer[] tree)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's