Validate Binary Search Tree LeetCode Solution | Easy Approach

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 Solutions

✅Time:  $O(n)$
✅Space:  $O(n)$

C++

class Solution {
 public:
  bool isValidBST(TreeNode* root) {
    return isValidBST(root, nullptr, nullptr);
  }

 private:
  bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
    if (!root)
      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);
  }
};

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);
  }
}

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)

Watch Tutorial

Checkout more Solutions here