Validate Binary Search Tree
Medium · Trees · Tree · DFS · Binary Search Tree
Problem
Decide whether a binary tree is a valid binary search tree.
Valid means: every value in a node's left subtree is strictly smaller than the node, every value in its right subtree is strictly larger, and both subtrees are themselves valid.
from_level() is provided.
Examples
Input: root = [2,1,3] Output: True
1 < 2 < 3.
Input: root = [5,1,4,None,None,3,6] Output: False
3 sits in 5's right subtree but is smaller than 5, even though it is correctly placed under 4.
Constraints
- 1 <= number of nodes <= 10^4
- -2^31 <= Node.val <= 2^31 - 1
Approaches
- Carry an allowed range down — time O(n), space O(h)
Related problems
Start free on Cariara · Coding problems · System design studio
