<jupyter_start><jupyter_text>Given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:- The left subtree of a node contains only nodes with keys less than the node's key.- The right subtree of a node contains only nodes with keys greater than the node's key.- Both the left and right subtrees must also be binary search trees. Example 1:        2       / \      1   3    Input: [2,1,3]    Output: trueExample 2:        5       / \      1   4         / \        3   6    Input: [5,1,4,null,null,3,6]    Output: false    Explanation: The root node's value is 5 but its right child's value is 4.<jupyter_code># recursive solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        lst = self.inorderTraversal(root)
        for i in range(1,len(lst)):
            if lst[i-1] >= lst[i]:
                return False
        return True
    
    def inorderTraversal(self, root):
        '''
        :param root: TreeNode
        :return: List[int]
        '''
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.val)
            res += self.inorderTraversal(root.right)
        return res
# iterative solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        lst = self.inorderTraversal(root)
        for i in range(1,len(lst)):
            if lst[i-1] >= lst[i]:
                return False
        return True
    
    def inorderTraversal(self, root):
        '''
        :param root: TreeNode
        :return: List[int]
        '''
        # order: left -> root -> right
        res, stack = [], []
        while True:
            while root: 
                stack.append(root)  
                root = root.left    
                
            if not stack:
                return res
            
            node = stack.pop()
            res.append(node.val)

            root = node.right<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09967453213995119, 'fraction_numerical': 0.009764035801464606, 'mean_word_length': 1.6159574468085107, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '6931', 'license': 'MIT', 'n_tokens_mistral': 735, 'n_tokens_neox': 705, 'n_words': 230, 'path': 'DSA/tree/isValidBST.ipynb', 'repo_name': 'lance-lh/Data-Structures-and-Algorithms', 'size': '2458'}