In this post, you will know how to solve the Validate Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Validate Binary Search Tree Leetcode Solutions in Python
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidBST(root: Optional[TreeNode],
minNode: Optional[TreeNode], maxNode: Optional[TreeNode]) -> bool:
if not root:
return True
if minNode and root.val <= minNode.val:
return False
if maxNode and root.val >= maxNode.val:
return False
return isValidBST(root.left, minNode, root) and \
isValidBST(root.right, root, maxNode)
return isValidBST(root, None, None)
Validate Binary Search Tree Leetcode Solutions in CPP
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, nullptr, nullptr);
}
private:
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (root == nullptr)
return true;
if (minNode && root->val <= minNode->val)
return false;
if (maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) &&
isValidBST(root->right, root, maxNode);
}
};
Validate Binary Search Tree Leetcode Solutions in Java
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode root, TreeNode minNode, TreeNode maxNode) {
if (root == null)
return true;
if (minNode != null && root.val <= minNode.val)
return false;
if (maxNode != null && root.val >= maxNode.val)
return false;
return isValidBST(root.left, minNode, root) &&
isValidBST(root.right, root, maxNode);
}
}
Note: This problem Validate Binary Search Tree is generated by Leetcode but the solution is provided by Brokenprogrammers. This tutorial is only for Educational and Learning purposes.
Next: Unique Binary Search Trees Leetcode Solution
