LeetCode 98. Validate Binary Search Tree

Description

https://leetcode.com/problems/validate-binary-search-tree/

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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:

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

Example 2:

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.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Explanation

A tree is a valid binary search tree when if its left subtree and right subtree are both valid binary search trees and its root value greater than the max value of the left subtree and its root value is less than the minimum value of the right subtree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        
        return self.helper(root, sys.maxsize, -sys.maxsize)
    
    def helper(self, root, max_value, min_value):
        if not root:
            return True
                
        left = self.helper(root.left, root.val, min_value)
        right = self.helper(root.right, max_value, root.val)
        
        return left and right and root.val < max_value and root.val > min_value
        

• Time complexity: O(N).
• Space complexity: O(N).