Validate Binary Search Tree
MediumTrees
Given the root of a binary tree, return True if it is a valid binary search tree (BST) and False otherwise.
A binary tree is a valid BST when, for every node:
- every value in its left subtree is strictly smaller than the node's value, and
- every value in its right subtree is strictly larger than the node's value.
Because the rule covers whole subtrees, comparing each node only with its direct children is not enough. Equal values are not allowed anywhere in a valid BST.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [5,1,7,null,null,4,8]
- Output:
- False
- Explanation
- 4 is a valid left child of 7, but it sits in the right subtree of 5 and is smaller than 5. Checking only parent against child would miss this, since the rule covers the whole subtree.
Example 2
- Input:
- root = [2,2,3]
- Output:
- False
- Explanation
- The left child equals the root, and the rule requires strictly smaller.
Example 3
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]
- Output:
- True
- Explanation
- Every node stays inside the range its ancestors allow, including 4 and 7, which must fall between 3 and 8, and 13, which must fall between 10 and 14.
Constraints
- The number of nodes is in the range
[1, 10^4] -2^31 <= Node.val <= 2^31 - 1- The tree height is at most
500