Skip to main content

98 - Validate Binary Search Tree

Details

KeyValue
Linkhttps://leetcode.com/problems/validate-binary-search-tree/
LanguagePython 3
Runtime103 ms, faster than 5.65% of Python3 online submissions for Validate Binary Search Tree
Memory Usage16.4 MB, less than 78.23% of Python3 online submissions for Validate Binary Search Tree
DatastructuresTreeNode
AlgorithmsRecursion
ComplexityTime: O(N) Memory: O(N)

Procedure

  1. ...

Code

# 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: Optional[TreeNode]) -> bool:
return self.validateBST(root, float("-inf"), float("inf"))

def validateBST(self, node, left, right):
# Empty tree is valid BST
if not node: return True

# Node value must be between left/right
if not left < node.val < right: return False

# Ensure left and right are valid
return (
self.validateBST(node.left, left, node.val) and
self.validateBST(node.right, node.val, right)
)