Findable Archive Records
Medium · tree dfs
An archive stores its records in a binary tree, meant to be used like a binary search tree: every record has a number, smaller numbers are supposed to sit to the left and larger numbers to the right. Over the years some records were misfiled, so the tree may no longer be a proper search tree.
To look up a record number v, a clerk starts at the root and repeats:
- if the current record has number
v, stop: the lookup ends at this record; - if
vis smaller than the current number, move to the left child; - otherwise move to the right child;
- if there is no child to move to, stop: the lookup ends with nothing found.
A record is findable if looking up its own number ends at that very record. Return how many records in the tree are findable.
Record numbers can repeat. When they do, a lookup always stops at the first matching record it meets, so a later record with the same number may not be findable. An empty tree has no records, so return 0.
Examples
Example 1
Input: root = [5, 3, 8, 1, 6, 7, 9]
Output: 6
Looking up 6 goes from 5 to the right (8), then to the left (7), then to the left again and finds nothing. So 6 is misfiled. The other six records are findable.
Example 2
Input: root = [4, 2, 6, 1, 3, 5, 7]
Output: 7
This is a proper search tree, so every record is findable.
Example 3
Input: root = [2, 2, 2]
Output: 1
Every lookup for 2 stops at the root, so only the root is findable.
Constraints
- The number of nodes is in the range [0, 2500].
- -10^6 <= Node.val <= 10^6. Values may repeat.