A library index is meant to be a binary search tree: for every node, every value in its left subtree is strictly smaller and every value in its right subtree is strictly larger. Duplicates are not allowed.
Print YES if the given tree follows the rule and NO otherwise.
Constraints
- 1 ≤ number of nodes ≤ 10000
- values fit in 32-bit signed integers
Input and output
- Input
- Line 1: n, the number of tokens. Line 2: the tree in level order — n tokens, each an integer or `null` for a missing child (trailing nulls may be left out).
- Output
- `YES` or `NO`.
Examples
Input 1
3
8 3 10Output
YES3 < 8 < 10, so it is a valid search tree.
Input 2
7
8 3 10 null null 6 12Output
NO6 sits in the right subtree of 8 but is smaller than 8, so the tree is not valid.
Show hints
- Checking each node only against its two children is not enough.
- Pass down the open interval (low, high) that every node in a subtree must fall in.
Show the explanation
The common mistake is to compare a node only with its children; the second sample passes that test but fails because 6 is in the right subtree of 8. Instead, recurse with bounds: the root may be anything; a left child inherits (low, parent) and a right child inherits (parent, high). Every node must satisfy low < value < high. An equivalent check is that an in-order traversal is strictly increasing.
Original UniCircle question. Last reviewed 22 Oct 2026.