# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    '''
    Time Complexity: O(n), where n is the number of nodes in the tree.
    Space Complexity: O(n)
    Every node is visited exactly once and each visit is O(1), so time is O(n) whatever the
    shape. Measured 2n+1 calls on every tree tried, skewed and balanced alike, because the
    n+1 empty slots are visited too.

    Space is the recursion stack, so it is really O(h) for height h: O(log n) on a balanced
    tree, O(n) on a fully skewed one, which is the bound quoted above. Measured max depth 15
    on a balanced n=10000 against 10001 on a skewed n=10000.

    Re-solve, not a first pass. The 2024 attempt above is the same algorithm, so 5m 28s is
    recall speed rather than solve speed. Worth keeping both: the chained comparison states
    the invariant once, where the older `<= minNeeded or >= maxAllowed` states the two ways
    to fail and reads node.val twice.
    '''
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def validSubBST(minVal, maxVal, node):
            if not node:
                return True
            if not minVal < node.val < maxVal:
                return False
            return validSubBST(minVal,node.val,node.left) and validSubBST(node.val,maxVal,node.right)

        return validSubBST(float('-inf'),float('inf'),root)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        '''
        Time Complexity: O(n), where n is the number of nodes in the tree.
        We would check each node exactly once, so time complexity is O(n).
        '''
        return self.isValidChild(root, float('-inf'), float('inf'))
    def isValidChild(self, root: Optional[TreeNode], minNeeded: int, maxAllowed: int) -> bool:
        if root == None:
            return True
        if root.val <= minNeeded or root.val >= maxAllowed:
            return False
        return self.isValidChild(root.left, minNeeded, root.val) and self.isValidChild(root.right, root.val, maxAllowed)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public boolean isValidBST(TreeNode root) {
    return isValidChild(root, null, null);
}
public boolean isValidChild(TreeNode node, Integer minLimit, Integer maxLimit) {
    /*
    * Do not fall into a pitfall by hardcoding Min and Max limits with Integer.MAX_VALUE.
    * If you do that, and if one of the test cases have their root value as Integer.MAX_VALUE, it would return false, although the BST is valid.
    * Example test case: [Integer.MAX_VALUE]
    * A single node BST with max int value is valid!
    */
    if (node == null) {
        return true;
    }
    if ((minLimit != null && node.val <= minLimit) || (maxLimit != null && node.val >= maxLimit)) {
        return false;
    }
    return isValidChild(node.left, minLimit, node.val) && isValidChild(node.right, node.val, maxLimit);
}