Here, We see Validate Binary Search Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Validate Binary Search Tree LeetCode Solution
Table of Contents
Problem Statement
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.
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.
Validate Binary Search Tree Leetcode Solution C++
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);
}
};
Code language: PHP (php)
Validate Binary Search Tree Leetcode Solution Java
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}
Code language: PHP (php)
Validate Binary Search Tree Leetcode Solution JavaScript
var isValidBST = function(root) {
function inOrder(node) {
if(!node) return [];
return [...inOrder(node.left), node.val, ...inOrder(node.right)]
}
const sortedArr = inOrder(root);
for(let i = 0; i < sortedArr.length; i++) {
if(sortedArr[i+1] <= sortedArr[i]) return false;
}
return true;
};
Code language: JavaScript (javascript)
Validate Binary Search Tree Leetcode Solution Python
class Solution(object):
def isValidBST(self, root):
stack = [None]
prev = -float("inf")
while stack:
while root:
stack.append(root)
root = root.left
x = stack.pop()
if x:
if x.val <= prev:
return False
prev = x.val
root = x.right
return True
Code language: HTML, XML (xml)