Validate Binary Search Tree
Validate Binary Search Tree is a medium Trees problem from the Blind 75. The key pattern is bounds recursion, and a good solution runs in O(n) time.
Problem
Determine whether a level-order tree is a strict BST: every left value is smaller and every right value is larger.
Examples
Example 1
Input
[8,3,12,1,6,10,14]Output
trueExample 2
Input
[4,2,6]Output
trueExample 3
Input
[8,3,10,null,null,7,12]Output
falseApproach
Pass down the open interval every node must fit in: going left tightens the upper bound, going right the lower bound.
| Pattern | Bounds recursion |
|---|---|
| Time | O(n) |
| Space | O(h) |
Watch out for
Checking only a node against its children is not enough, and equal values are not allowed.