Description:
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.
Examples:
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.Solution in Python:
To determine if a binary tree is a valid Binary Search Tree (BST), we need to ensure that for every node, all the nodes in its left subtree have values less than the node’s value, and all the nodes in its right subtree have values greater than the node’s value. Additionally, both left and right subtrees must also be BSTs.
To solve this problem in Python, we will use a recursive approach where we pass down the valid range of values for each node. For the root node, the range is initially (-infinity, +infinity). For each node, we adjust the range for its left and right children:
- For the left child, the valid range becomes
(lower_bound, current_node_value) - For the right child, the valid range becomes
(current_node_value, upper_bound)
Python
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# Helper function to validate the BST with boundary values
def validate(node, low=float('-inf'), high=float('inf')):
# An empty node/subtree is considered valid
if not node:
return True
# The current node's value must be within the range defined by low and high
if not (low < node.val < high):
return False
# Recursively validate the left and right subtrees with updated boundaries
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
# Start the validation from the root node
return validate(root)Explanation of the Code
- Base Case:
- If the current node is
None(i.e., the subtree is empty), it’s considered a valid BST, so returnTrue.
- If the current node is
- Range Validation:
- Check if the current node’s value lies within the valid range
[low, high). If it does not, returnFalse.
- Check if the current node’s value lies within the valid range
- Recursive Validation:
- Recursively validate the left subtree with an updated upper bound (
node.val). - Recursively validate the right subtree with an updated lower bound (
node.val).
- Recursively validate the left subtree with an updated upper bound (
- Initialization:
- Start the validation process from the root node with the initial range of
(-infinity, +infinity).
- Start the validation process from the root node with the initial range of
This approach ensures that every node’s value in the tree satisfies the BST property relative to its parent and subtree nodes. The use of boundary values helps maintain the constraints and ensures that the tree remains a valid BST.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
// Helper function to validate the BST with boundary values
const validate = function(node, low, high) {
// An empty node/subtree is considered valid
if (node === null) {
return true;
}
// The current node's value must be within the range defined by low and high
if (node.val <= low || node.val >= high) {
return false;
}
// Recursively validate the left and right subtrees with updated boundaries
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
};
// Start the validation from the root node with initial range of (-infinity, +infinity)
return validate(root, -Infinity, Infinity);
};Solution in Java:
Java
class Solution {
public boolean isValidBST(TreeNode root) {
// Helper function to validate the BST with boundary values
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long low, long high) {
// An empty node/subtree is considered valid
if (node == null) {
return true;
}
// The current node's value must be within the range defined by low and high
if (node.val <= low || node.val >= high) {
return false;
}
// Recursively validate the left and right subtrees with updated boundaries
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}
}Solution in C#:
C#
public class Solution {
public bool IsValidBST(TreeNode root) {
// Helper function to validate the BST with boundary values
return Validate(root, long.MinValue, long.MaxValue);
}
private bool Validate(TreeNode node, long low, long high) {
// An empty node/subtree is considered valid
if (node == null) {
return true;
}
// The current node's value must be within the range defined by low and high
if (node.val <= low || node.val >= high) {
return false;
}
// Recursively validate the left and right subtrees with updated boundaries
return Validate(node.left, low, node.val) && Validate(node.right, node.val, high);
}
}