Valid Search Tree
You are given the root of a binary tree. Return whether it is a binary search tree, which means that for every node:
- every value in its left subtree is smaller than the node's value,
- every value in its right subtree is larger than the node's value.
Equal values are not allowed anywhere in a search tree.
Trees in the examples are written level by level, left to right, with null where a child is missing: [1,null,2] is a root 1 with only a right child, 2. [] is an empty tree, with no root at all.
Constraints
- 1 ≤ number of nodes ≤ 10,000
- -2³¹ ≤ node value ≤ 2³¹ - 1 (the whole range of a 32-bit int)
- The tree is at most 1,000 levels deep.
Example 1
Input
root = [2,1,3]
Output
true
Why:
1 is smaller than 2 and 3 is larger.
Example 2
Input
root = [5,1,4,null,null,3,6]
Output
false
Why:
4 is in the root's right subtree, but it is smaller than 5.
Example 3
Input
root = [10,5,15,null,null,6,20]
Output
false
Why:
6 is fine next to its parent 15, but it is in the right subtree of 10, so it must be larger than 10.
Hints
Was this a good challenge?
- Solved by
- 0
- Submissions
- 0
- Accepted
- –