Validate Binary Search Tree

Problem Statement

You’re a BST inspector ensuring a binary tree follows the rules: left subtree < root < right subtree, recursively. Return true if it’s a valid BST, false otherwise. This medium-level recursive challenge is a structural audit—check those bounds!

Example

Input: root = [2,1,3]

Tree:

  2
 / \
1   3

Output: true

Input: root = [5,1,4,null,null,3,6]

Tree:

  5
 / \
1   4
   / \
  3   6

Output: false (3 < 4 but > 5 violates BST)

Input: root = [1]

Output: true

Code

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}
            

class Solution:
    def isValidBST(self, root):
        def validate(node, min_val, max_val):
            if not node:
                return True
            if node.val <= min_val or node.val >= max_val:
                return False
            return validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)
        return validate(root, float('-inf'), float('inf'))
            

function isValidBST(root) {
    function validate(node, min, 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);
    }
    return validate(root, -Infinity, Infinity);
}
            

Explanation

• DFS Insight: Each node must satisfy a range based on its ancestors.
• Flow: Recursively check left < root < right, updating bounds (min, max).
• Example Walkthrough: [5,1,4,null,null,3,6] → 4 fails (3 < 5 needed, but 3 < 4 < 5).
• Key Detail: Use long/float to handle edge values like Integer.MIN_VALUE.
• Inorder Alt: Check if inorder traversal is strictly increasing—also O(n).

Note