Validate the whole BST

Validate a binary tree against the global BST rule: every key in a left subtree is smaller than its ancestor and every key in a right subtree is larger. The tree is serialized in preorder with N for null pointers.

Input

— The first line contains T.
— Each case starts with token count m, followed by m preorder tokens; each token is an integer or N.

Output

Print YES when the entire tree is a valid BST; otherwise print NO.

Technique

recursive range propagation

Target

O(n)

Constraints & sample

1 ≤ m ≤ 400,001
Integer keys are distinct
The serialization is valid

Sample input

3
7
5 3 N N 7 N N
7
5 7 N N 3 N N
11
10 5 N N 15 6 N N 20 N N

Expected output

YES
NO
NO

Review the concept

Before you submit

Test the smallest valid input and one awkward edge case.
Keep the solution within O(n).
Match spacing and line breaks exactly before checking 8 hidden cases.

Draft saved locally · 918 / 30,000

Ln 1, Col 1Spaces: 4UTF-8LFC++17

Visible testcases

Editable and stored only in this browser. Hidden judge cases never change.

Input (stdin)Include T when the problem expects it

3
7
5 3 N N 7 N N
7
5 7 N N 3 N N
11
10 5 N N 15 6 N N 20 N N

61 charsExpected outputExact output, ignoring trailing spaces

YES
NO
NO

9 chars

Checking your session…

Run checks Sample · Submit checks 8 hidden cases

Run the sample first, then send your solution through 8 hidden cases.

Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.