A database stores keys that may repeat. Its tree must satisfy this rule at every node: all values in the left subtree are less than or equal to the node's value, and all values in the right subtree are strictly greater. Return True if the whole tree follows the rule, otherwise False. An empty tree is valid.
Examples
5
/ \
5 8
/
3
Input: root = build_tree([5, 5, 8, 3])
Output: True
Input: root = build_tree([5, 3, 5]) (a 5 on the right of 5)
Output: False
10
/ \
5 15
\
12
Input: root = build_tree([10, 5, 15, None, 12])
Output: False (12 is in the left subtree of 10 but larger than 10)
Constraints
0 <= number of nodes <= 3000- Values are integers
- O(n) time
Goals
- Pass value bounds down the recursion
- Apply an asymmetric rule: inclusive on the left, strict on the right