A product catalog is indexed by a binary tree of integer keys. You must decide whether the tree is a strict binary search tree (BST): for every node, every key in its left subtree is strictly less than the node's key, and every key in its right subtree is strictly greater than the node's key. Duplicate keys are therefore never allowed.
The tree is given in level-order (breadth-first) form: the tokens list the root, then the children of each node left-to-right, using the token null for a missing child. Trailing null tokens are omitted.
Line 1: an integer n, the number of level-order tokens.
Line 2: n space-separated tokens, each either an integer key or the literal null. The first token is the root and is never null.
Print YES if the tree is a strict BST, otherwise print NO.
Example 1
Input
5 8 3 10 1 6
Expected
YES
Explanation
Root 8 has left child 3 (with children 1 and 6) and right child 10. Every key in the left subtree (3, 1, 6) is < 8, every key in the right subtree (10) is > 8, and 1 < 3 < 6 holds, so it is a strict BST: YES.
Example 2
Input
3 5 5 7
Expected
NO
Explanation
The left child 5 equals the root 5. A strict BST requires strictly smaller keys on the left, so the equal key breaks the property: NO.
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 →