98. Validate Binary Search Tree

Solution 1: DFS

class Solution:
    def _isValidBST(self, root, minNode, maxNode):
        if not root:
            return True
        
        # 1. Not all the nodes in the left less than root
        # 2. Not all the nodes in the right greater than root
        if (maxNode and root.val >= maxNode.val) or (minNode and root.val <= minNode.val):
            return False
        else:
            isLftSubTreeValidBST = self._isValidBST(root.left, minNode, root)
            isRhtSubTreeValidBST = self._isValidBST(root.right, root, maxNode)
            return isLftSubTreeValidBST and isRhtSubTreeValidBST
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self._isValidBST(root, None, None)

Time Complexity: O(N)
Space Complexity: O(N) // The recursive call need O(N) stack in worst case

Solution 2: BFS (Level-Order)

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Inorder Traverse

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/validate-binary-search-tree/discuss/32141/C%2B%2B-simple-recursive-solution
https://leetcode.com/problems/validate-binary-search-tree/discuss/32109/My-simple-Java-solution-in-3-lines
https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)
https://leetcode.com/problems/validate-binary-search-tree/discuss/32104/C%2B%2B-in-order-traversal-and-please-do-not-rely-on-buggy-INT_MAX-INT_MIN-solutions-any-more
https://leetcode.com/problems/validate-binary-search-tree/discuss/786520/General-Tree-Traversal-Problems-interview-Prep