Validate Binary Search Tree
MediumP1Coding
Given the root of a binary tree, return true if it is a valid binary search tree, otherwise false.
In a valid BST, for every node every value in its left subtree is strictly less than the node's value, and every value in its right subtree is strictly greater. Duplicates make a tree invalid. An empty tree is valid.
Tree nodes have val, left and right. The class TreeNode is already defined for you. The tree arrives in level-order form (as in the examples) and you receive its root, which is null for an empty tree.
Example 1
- Input
- root = [2,1,3]
- Output
- true
Example 2
- Input
- root = [5,1,4,null,null,3,6]
- Output
- false
- Why
- Node 3 is in the right subtree of 5 but is smaller than 5.
Example 3
- Input
- root = [2,2,2]
- Output
- false
Constraints
- The number of nodes is in the range [0, 10^4].
- -2^31 <= Node.val <= 2^31 - 1
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 12. ⌘Enter runs, ⌘⇧Enter submits.