Algorithm
Problem Nmae: 98. Validate Binary Search Tree
problem Link: 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
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool isValid(struct TreeNode* p, struct TreeNode** prev) {
if (!p) return true;
if (!isValid(p->left, prev)) return false;
if (*prev && p->val < = (*prev)->val) return false;
*prev = p;
return (isValid(p->right, prev));
}
bool isValidBST(struct TreeNode* root) {
struct TreeNode *prev = NULL;
return isValid(root, &prev);
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(!root) return true;
if(!isValid(root->left, root->val, true) || !isValid(root->right, root->val, false)) return false;
return isValidBST(root->left) && isValidBST(root->right);
}
bool isValid(TreeNode* root, int bound, bool isLeft){
return !root || (isLeft ? root->val < bound : root->val > bound ) && isValid(root->left, bound, isLeft) && isValid(root->right, bound, isLeft);
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, (((long) Integer.MAX_VALUE) + 1), ((long) Integer.MIN_VALUE) - 1);
}
private boolean isValidBSTHelper(TreeNode node, long max, long min) {
if (node == null) {
return true;
}
if (node.val >= max || node.val < = min) {
return false;
}
return isValidBSTHelper(node.left, node.val, min) && isValidBSTHelper(node.right, max, node.val);
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isValidBST = function(root) {
return helper(root, -Infinity, Infinity)
}
function helper(root, minValue, maxValue) {
if (!root) return true
if (root.val <= minValue || root.val >= maxValue) {
return false
}
let leftSide = helper(root.left, minValue, root.val)
let rightSide = helper(root.right, root.val, maxValue)
return leftSide && rightSide
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def validate(node, mn, mx):
if not node: return True
if node.valmx: return False
return validate(node.left,mn,node.val-1) and validate(node.right,node.val+1,mx)
return validate(root, -float("inf"),float("inf"))
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _098_ValidateBinarySearchTree
{
public bool IsValidBST(TreeNode root)
{
return IsValidBST(root, long.MinValue, long.MaxValue);
}
public bool IsValidBST(TreeNode current, long low, long high)
{
if (current == null) return true;
if (current.val < = low || current.val >= high) return false;
return IsValidBST(current.left, low, current.val) && IsValidBST(current.right, current.val, high);
}
}
}
Input
Output