Given the root of a binary tree, return true if it is a valid binary search tree and false otherwise.
In a valid binary search tree, for every node:
9 sits correctly to the right of 3, but it is inside the left subtree of 8, where every value must be smaller than 8.
Constraints
1 and 10⁴ nodes.-2³¹ <= Node.val <= 2³¹ - 1Checking each node against its children alone is not enough: a node deep in the left subtree must still be smaller than the root.
The tempting check is local: at each node, is the left child smaller and the right child larger? Example 2 shows why that isn't enough. 9 is a fine right child for 3, yet it lives inside the left subtree of 8, and everything there has to be below 8.
Time O(n)Space O(h)
The full walkthrough and code are part of Premium
true