LeetCode Problem 98: Validate Binary Search Tree(BST) Solution in C++, Java, Python

🔍 Problem Overview

You’re given the root of a binary tree—your task is to determine whether it’s a valid Binary Search Tree (BST).

BST Definition:

1. Left subtree nodes < current node.
2. Right subtree nodes > current node.
3. Both subtrees must also be valid BSTs.

Example:

• ✅ Valid: [2,1,3]
• ❌ Invalid: [5,1,4,null,null,3,6] (3 is in the right subtree but < 5)

💡 Solution Approach – Recursive Min/Max Validation

A valid BST ensures each node’s value falls within a specific range.

Core Idea:

• At each node, ensure: min < node.val < max
• Left child: max = current node’s value
• Right child: min = current node’s value

Steps:

1. Base case: If node is null, it’s valid.
2. Check if current node lies within bounds.
3. Recursively validate left and right subtrees with updated bounds.

🧠 Code Implementations

✅ Java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}

✅ C++

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

    bool validate(TreeNode* node, long long min, long long max) {
        if (!node) return true;
        if (node->val <= min || node->val >= max) return false;
        return validate(node->left, min, node->val) && validate(node->right, node->val, max);
    }
};

✅ Python

class Solution:
    def isValidBST(self, root):
        return self._validate(root, float('-inf'), float('inf'))

    def _validate(self, node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return self._validate(node.left, min_val, node.val) and self._validate(node.right, node.val, max_val)

⏱️ Complexity Analysis

• Time: O(N) – Visit each node once.
• Space: O(H) – Recursion stack (H = height of tree; O(N) in worst-case).

⚠️ Edge Cases to Test

• Empty tree → ✅ Valid
• One node → ✅ Valid
• Duplicate nodes → ❌ Invalid (strict inequality required)
• Extreme values like Integer.MIN_VALUE and Integer.MAX_VALUE → Handled using long or float('-inf')

🧾 FAQ – Clarified

1. Why use Long.MIN/MAX or float('-inf')?
To handle edge cases like Integer.MIN_VALUE and avoid overflow.

2. Can a BST have duplicates?
No. BSTs require strict ordering: left < parent < right.

3. What if a node equals the min or max bound?
Still invalid. Bounds must be exclusive.

4. Why not just check children?
Because a descendant (not just direct children) may violate BST rules.

👩‍💻 Interview Essentials

Q1: What’s the time/space complexity?

• Time: O(N), Space: O(H)

Q2: How would you write an iterative version?
Use a stack (DFS) with node + min/max bounds.

Q3: Can you do it with in-order traversal?
Yes. A valid BST will yield an increasing sequence during in-order traversal.

Q4: What if duplicates are allowed?
Modify checks:

• Left: <=
• Right: >

✅ Key Takeaways

• A valid BST must respect global constraints, not just local ones.
• The min/max recursion technique is clean, intuitive, and effective.
• Other alternatives like iterative DFS and in-order traversal are equally valid depending on the scenario.

Ready to crush that interview? This BST check is now part of your arsenal. 🚀 Let me know if you’d like an iterative or in-order solution too!