validate_binary_search_tree
1from typing import Optional 2from utils import TreeNode 3from math import inf 4 5 6# @leet start 7class Solution: 8 def isValidBST(self, root: Optional[TreeNode]) -> bool: 9 """ 10 This function determines whether a given binary search tree is valid. 11 The property of a binary search tree is as follows: 12 The node's value is greater than the value of its left child, but 13 less than the value of its right child. 14 15 This goes all the way down the tree. 16 Thus, for the first node, we allow any value for the root. 17 For the left subtree, the value can be within [-inf..node.val] 18 For the right subtree, the value can be within [node.val..inf] 19 So, the condition for checking for the validity of the left subtree is 20 that it must fall between [previously_allowed_min..node.val] 21 And for the right subtree, [node.val..previosuly_allowed_max] 22 We pass this condition through the tree to get the desired result. 23 """ 24 25 def traverse(node, min_allowed, max_allowed): 26 if not node: 27 return True 28 node_valid = min_allowed < node.val < max_allowed 29 left_valid = traverse(node.left, min_allowed, node.val) 30 right_valid = traverse(node.right, node.val, max_allowed) 31 return all([node_valid, left_valid, right_valid]) 32 33 return traverse(root, -inf, inf) 34 35 36# @leet end 37 38 39def test(): 40 assert 2 + 2 == 4
class
Solution:
8class Solution: 9 def isValidBST(self, root: Optional[TreeNode]) -> bool: 10 """ 11 This function determines whether a given binary search tree is valid. 12 The property of a binary search tree is as follows: 13 The node's value is greater than the value of its left child, but 14 less than the value of its right child. 15 16 This goes all the way down the tree. 17 Thus, for the first node, we allow any value for the root. 18 For the left subtree, the value can be within [-inf..node.val] 19 For the right subtree, the value can be within [node.val..inf] 20 So, the condition for checking for the validity of the left subtree is 21 that it must fall between [previously_allowed_min..node.val] 22 And for the right subtree, [node.val..previosuly_allowed_max] 23 We pass this condition through the tree to get the desired result. 24 """ 25 26 def traverse(node, min_allowed, max_allowed): 27 if not node: 28 return True 29 node_valid = min_allowed < node.val < max_allowed 30 left_valid = traverse(node.left, min_allowed, node.val) 31 right_valid = traverse(node.right, node.val, max_allowed) 32 return all([node_valid, left_valid, right_valid]) 33 34 return traverse(root, -inf, inf)
9 def isValidBST(self, root: Optional[TreeNode]) -> bool: 10 """ 11 This function determines whether a given binary search tree is valid. 12 The property of a binary search tree is as follows: 13 The node's value is greater than the value of its left child, but 14 less than the value of its right child. 15 16 This goes all the way down the tree. 17 Thus, for the first node, we allow any value for the root. 18 For the left subtree, the value can be within [-inf..node.val] 19 For the right subtree, the value can be within [node.val..inf] 20 So, the condition for checking for the validity of the left subtree is 21 that it must fall between [previously_allowed_min..node.val] 22 And for the right subtree, [node.val..previosuly_allowed_max] 23 We pass this condition through the tree to get the desired result. 24 """ 25 26 def traverse(node, min_allowed, max_allowed): 27 if not node: 28 return True 29 node_valid = min_allowed < node.val < max_allowed 30 left_valid = traverse(node.left, min_allowed, node.val) 31 right_valid = traverse(node.right, node.val, max_allowed) 32 return all([node_valid, left_valid, right_valid]) 33 34 return traverse(root, -inf, inf)
This function determines whether a given binary search tree is valid. The property of a binary search tree is as follows: The node's value is greater than the value of its left child, but less than the value of its right child.
This goes all the way down the tree. Thus, for the first node, we allow any value for the root. For the left subtree, the value can be within [-inf..node.val] For the right subtree, the value can be within [node.val..inf] So, the condition for checking for the validity of the left subtree is that it must fall between [previously_allowed_min..node.val] And for the right subtree, [node.val..previosuly_allowed_max] We pass this condition through the tree to get the desired result.
def
test():