[Leetcode] 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

initial

So diff between binary tree and bst is bst's inorder is in ascending order (i.e. root's left is always smaller than root and root is always smaller than root.right) as mentioned in https://velog.io/@whitehousechef/Binary-tree-Binary-search-tree

Solving the previous question of https://velog.io/@whitehousechef/Leetcode-530.-Minimum-Absolute-Difference-in-BST showed me that this question can be solved with a similar approach.

Inorder traversal and if any prev node is bigger or equal to current node, it is invalid bst.

solution

my workign sol

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None
        flag=False
        def inorder(node):
            nonlocal prev,flag
            if flag:
                return 
            if not node:
                return 
            inorder(node.left)
            if prev:
                if node.val<=prev.val:
                    flag=True
            prev=node
            inorder(node.right)
            return 
        inorder(root)
        return False if flag else True

or refactored to be

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None

        def inorder(node):
            nonlocal prev
            if not node:
                return True

            if not inorder(node.left):
                return False

            if prev and node.val <= prev.val:
                return False

            prev = node
            return inorder(node.right)

        return inorder(root)

complexity

o(n) time
space worse case is o(n) but for balanced, it is log n cuz
maximum depth of the recursion would be proportional to the height, resulting in a space complexity of O(log n).