[LeetCode] 98. Validate Binary Search Tree

Problem : https://leetcode.com/problems/validate-binary-search-tree/

In-order traversing a BST generates an ascending sequence.  Use this BST characteristic to valid the given BST.

Time Complexity = O ( N ).   N = total nodes of the BST.

# 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: TreeNode) -> bool:
        
        def inorder(node, pre_val):
            if node:
                result = inorder(node.left, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                
                pre_val = result[0]
                
                if pre_val != None and pre_val >= node.val:
                    return (pre_val, False)
                
                pre_val = node.val
                
                result = inorder(node.right, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                    
                return result
            else:
                return (pre_val, True)
            
        
        return inorder(root, None)[1]

For a valid BST, values on left child tree must be in range [-2**31, root.val) and values on right child tree must be in range (root.val, 2**31-1]

Check if values in left / right sub-trees fall into the valid range.

# 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: TreeNode) -> bool:
        if not root: return True
        
        def inorder(node, mi, mx):
            if node.left:
                if not inorder(node.left, mi, node.val - 1):
                    return False
            
            if mx != None and node.val > mx:
                return False
            
            if mi != None and node.val < mi:
                return False
            
            if node.right:
                return inorder(node.right, node.val + 1, mx)
            
            return True
        
        return inorder(root, None,  None)