Problem A
BST Debugging
Øyvind has recently implemented a binary search tree. However, there seems to be some problems with his implementation – some searches does not behave correctly. To debug his implementation he added a print statement whenever a key is examined in the tree, so he can find where it goes wrong.
Now the only problem is identifying which of these sequences of examined keys are invalid in a proper binary search tree. Can you write a program that checks if a sequence of keys examined in a search is valid?
Input
The first line consists of two integeres, $n$ ($1 \leq n \leq 100\, 000$), the number of keys examined in a given search, and $m$ ($-2^{31} \leq m < 2^{31}$), the key that is searched for. The next line contains $n$ space-separated keys (all $32$-bit signed integers) in the order they are examined by the search.
Output
Output “valid” if the sequence of keys examined is plausible in a correctly implemented BST, or “invalid” otherwise. There is no guarantee that the search tree is balanced, or that the search key exists in the tree.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 10 20 15 5 9 11 |
valid |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 0 1 4 5 |
invalid |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 0 72 -500 32 16 8 7 -200 0 |
valid |
