98. Validate Binary Search Tree LeetCode Solution

In this guide, you will get 98. Validate Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Validate Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Validate Binary Search Tree solution in C++
4. Validate Binary Search Tree solution in Java
5. Validate Binary Search Tree solution in Python
6. Additional Resources

Problem Statement of 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 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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

98. Validate Binary Search Tree LeetCode Solution in C++

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);
  }
};
/* code provided by PROGIEZ */

98. Validate Binary Search Tree LeetCode Solution 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);
  }
}
// code provided by PROGIEZ

98. Validate Binary Search Tree LeetCode Solution in Python

class Solution:
  def isValidBST(self, root: TreeNode | None) -> bool:
    def isValidBST(root: TreeNode | None,
                   minNode: TreeNode | None, maxNode: TreeNode | None) -> 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)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.