BinarySearch 0069 Binary Search Tree Validation

Problem statement

https://binarysearch.com/problems/Binary-Search-Tree-Validation/

Solution

Equal to Leetcode 0098. Validate Binary Search Tree

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        def dfs(node, low, high):
            if not node: return True
            
            if not low < node.val < high: return False
            
            return dfs(node.right, node.val, high) and dfs(node.left, low, node.val)
        
        return dfs(root, -float("inf"), float("inf"))