LC98 Validate Binary Search Tree

# 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 O(N)  space O(H)
    # main idea: find cases that not meet valid criteria at each node 
    def isValidBST(self, root: TreeNode) -> bool:
        return self._traverse(root,float('-inf'),float('inf'))
    
    def _traverse(self,node,lower,upper):
        #step1:  termination condition
        if not node:
            return True 
        #step2:  inorder traversal 
        val = node.val
        if not self._traverse(node.left,lower,val):
            return False
        if not self._traverse(node.right,val,upper):
            return False
        #step3: set up criteria to be invalidate
        if node.val <= lower or node.val >= upper:
            return False
        return True

# 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 O(N)  space O(H)
    # main idea: find cases that not meet valid criteria at each node 
    def isValidBST(self, root: TreeNode) -> bool:
#step1: create a stack, put root, lower, upper into the stack as tuple 
        stack = [(root,float('-inf'),float('inf'))]
#step2: set up termination condition:  stack is empty         
        while stack:
            node, lower, upper = stack.pop()
            # edge case: node is None
            if not node:
                continue
            val = node.val    
            #step3:(inorder traverse) at each node, compare lower and upper,  if not meet, return False 
            if val >= upper or val <= lower:
                return False
            #step4:  push node.right and node.left back to stack 
            stack.append((node.right,val,upper))
            stack.append((node.left,lower,val))
        return True