503. Search Tree Audit
An inspector must confirm that a binary tree handed over by a warehouse system is a proper binary search tree. A tree qualifies when, for every node, every key anywhere in its left subtree is strictly smaller than the node's key and every key anywhere in its right subtree is strictly larger. Comparing a node only with its direct children is not enough, and equal keys are not allowed.
Given root, return true if the tree satisfies this rule and false otherwise. An empty tree and a tree with a single node both qualify.
Example 1
- Input:
- root = [18,7,25,3,11,20,31]
- Output:
- true
- Explanation:
Every key is larger than all keys on its left and smaller than all keys on its right, so the tree is a valid search tree.
Example 2
- Input:
- root = [18,7,25,3,11,12,31]
- Output:
- false
- Explanation:
The key 12 lies in the right subtree of 18 but is smaller than 18, so the ordering rule is broken.
Constraints
0 ≤ number of nodes ≤ 104
-231 ≤ Node.val ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)