A herbarium stores every pressed specimen in a binary search tree keyed by catalog ID: for any specimen, every catalog ID in its left branch is smaller than its own, and every catalog ID in its right branch is larger. The curator wants to know how tightly two specimens' catalog IDs can ever collide -- specifically, the smallest possible absolute difference between the catalog IDs of any two (distinct) specimens anywhere in the collection.
The tree is given as a breadth-first serialization. Line 1 contains a single integer m, the number of tokens on line 2. Line 2 contains m space-separated tokens, each either a non-negative integer (a catalog ID) or the literal token "N" (meaning that child position does not exist).
The serialization is built with a queue, starting from the root: the first token is always the root's catalog ID (never "N"). Then, repeatedly, take the next node out of the queue and read its left-child token followed by its right-child token from the next two unread tokens in the list. If a child's token is "N", that child does not exist and contributes no further tokens. If it is an integer, a new node with that catalog ID is created, and it is enqueued so that its own two children will later be read from the following tokens in the same way. This continues until every node that was enqueued has had its two child tokens read.
A single integer: the minimum absolute difference between any two catalog IDs in the tree.
Example 1
Input
11 4 2 6 1 3 N N N N N N
Expected
1
Explanation
The serialization decodes to a tree rooted at catalog ID 4, with left child 2 (whose children are 1 and 3) and right child 6 (no children). The full set of catalog IDs is {1, 2, 3, 4, 6}. Sorted, the consecutive gaps are 1, 1, 1, 2, so the minimum absolute difference is 1.
Example 2
Input
11 1 0 48 N N 12 49 N N N N
Expected
1
Explanation
The tree is rooted at 1, with left child 0 (no children) and right child 48 (whose children are 12 and 49). The full set of catalog IDs is {0, 1, 12, 48, 49}. Sorted, the consecutive gaps are 1, 11, 36, 1, so the minimum absolute difference is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →