A binary tree is a valid binary search tree if, for every node, all values in its entire left subtree are strictly less than the node's value, and all values in its entire right subtree are strictly greater. (Duplicate values make the tree invalid.) Decide whether the given tree is a valid BST.
One line: the binary tree as a level-order array.
The tree is encoded on ONE line as a space-separated level-order (breadth-first) array. The token null marks a missing child; the children of a null are omitted from the array. An empty tree is written as the single token null.
Print YES if the tree is a valid binary search tree, otherwise NO. An empty tree and a single node are valid.
Example 1
Input
5 3 8 2 4 7 9
Expected
YES
Explanation
In-order the values read 2 3 4 5 7 8 9, which is strictly increasing, so the tree is a valid BST: `YES`.
Example 2
Input
5 3 8 2 6
Expected
NO
Explanation
The value 6 sits in the left subtree of 5 but 6 > 5, breaking the BST rule, so `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 →