98. Validate Binary Search Tree
Note that in this version of a binary search trees, that duplicates are not allowed. The problem defines a binary search tree as:
- 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.
This problem and its solution is also in Cracking the Coding Interview book.
Suppose we have the following tree:
Atribution: Pat Hawks, CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0, via Wikimedia Commons
The idea to solve this problem is to think of a node as being between two values.
For the root node, 12, since it does not have a parent node, its value can be anything between negative infinity and infinity.
For the root's left child, its value must be between negative infinity and 12. In this case it is 6, so it is valid:
For the root's right child, its value must be between 12 and infinity. In this case it is 16, so it is valid:
Moving down the tree, we use the same formula for each node. So for node 6's left child its value must be between negative infinity and 6. For node 6's right child its value must be between 6 and 12.
And so on.
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def is_valid(node, left_val, right_val) -> bool:
if node is None:
return True
if not(left_val < node.val < right_val):
return False
return is_valid(node.left, left_val, node.val) and is_valid(node.right, node.val, right_val)
return is_valid(root, float("-INF"), float("INF"))