Leetcode 98. Validate Binary Search Tree

Problem

Leetcode 98 - Validate Binary Search Tree

Example:

Input: root = [2,1,3]
Output: true

Input: root = [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.

Approach

We can use DFS to check if the following BST is a valid BST. As we go in depth, we can check if node’s value is bigger than left and bigger than right. As we go in depth, we can update right value to root’s value for node.left, and we can update left value to root’s value for node.right.

Here is the Python code for the solution:

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root, left, right):
            if not root:
                return True
            
            if not (left < root.val < right):
                return False
            
            return dfs(root.left, left, root.val) and dfs(root.right, root.val, right)
        
        return dfs(root, float('-inf'), float('inf'))
    

Time Complexity and Space Complexity

Time Complexity: $O(n + m)$ where $m$ is length of nums1 $n$ is length of nums2

Space Complexity: $O(1)$