84. Validate Binary Search Tree
Verify that every node obeys the ordering requirements imposed by all its ancestors. Every value in a left subtree must be smaller, and every value in a right subtree must be larger.
Checking only immediate children misses violations deeper in a subtree. Equal values do not satisfy this course's strict BST ordering rule.
Example 1
Input
[2,1,3]
Output
true
Explanation: Every descendant satisfies its inherited interval.
Example 2
Input
[5,1,7,null,null,4,8]
Output
false
Explanation: 4 is less than its parent 7 but lies in root 5’s right subtree and must exceed 5.
Example 3
Input
[MIN,null,MAX]
Output
true
Explanation: Long exclusive bounds permit both int extremes.
Constraints
0 <= node count per tree <= 105-231 <= node.value <= 231 - 1- Each input is a proper binary tree: no cycles or shared child nodes. Null trees are permitted.
- A valid BST uses strict ordering; duplicate values are not allowed.
Hints
Hint 1
Can a grandparent impose a constraint the parent comparison misses?
Hint 2
Each node has an allowed open interval.
Hint 3
Pass (low,value) left and (value,high) right, with long outer sentinels.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Inherited exclusive intervals
[2,1,3]
true