AlgoExplained.dev

import math
Import the math module to access `math.inf` and `math.neg_inf` for representing unbounded initial range limits.
def isValidBST(root):
Defines the main function that takes the root of a binary tree and returns True if it is a valid BST, False otherwise.
    def validate(node, low=-math.inf, high=math.inf):
Defines the recursive helper with default bounds of negative and positive infinity. The root starts unconstrained; bounds tighten as we descend. Every node must satisfy `low < node.val < high`.
        if not node:
Base case: a null (empty) node is trivially a valid BST. This also terminates recursion at leaf children.
            return True
Return True for null nodes. An empty subtree does not violate any BST property.
        if node.val <= low or node.val >= high:
Check if the current node's value violates its allowed range. Values must be strictly within (low, high) — equal to either bound means the BST property is broken. Using `<=` and `>=` enforces strict inequality.
            return False
If the node's value is outside the valid range, immediately return False — no need to check further since the tree is already invalid.
        return (validate(node.left, low, node.val) and
Recurse into the left subtree with the upper bound tightened to `node.val`. All left descendants must be strictly less than this node.
                validate(node.right, node.val, high))
Recurse into the right subtree with the lower bound tightened to `node.val`. All right descendants must be strictly greater than this node. Both subtrees must be valid.
    return validate(root)
Kick off the recursion from the root with default bounds (-inf, +inf). Returns True only if every node in the entire tree passes its range check.

public boolean isValidBST(TreeNode root) {
Public entry point that takes the root of a binary tree and returns true if it is a valid BST. Delegates to the private validate helper with long bounds.
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
Start validation with the widest possible range using `long` type. `Long.MIN_VALUE` and `Long.MAX_VALUE` safely bound any `int` node value, including Integer.MIN_VALUE and Integer.MAX_VALUE.
}
End of the isValidBST method.
private boolean validate(TreeNode node, long low, long high) {
Private recursive helper that checks if a subtree rooted at `node` is a valid BST within the range (low, high). Using `long` parameters prevents overflow when comparing with int node values.
    if (node == null) return true;
Base case: null nodes are valid. This terminates recursion at leaf children and handles empty subtrees.
    if (node.val <= low || node.val >= high) return false;
Check if the node's value violates the allowed range. The comparison with `long` bounds works correctly even for Integer.MIN_VALUE and Integer.MAX_VALUE because `long` has a wider range.
    return validate(node.left, low, node.val) &&
Recurse left with the upper bound tightened to `node.val`. All left descendants must be strictly less than this node. `&&` short-circuits: if left is false, right is not checked.
           validate(node.right, node.val, high);
Recurse right with the lower bound tightened to `node.val`. All right descendants must be strictly greater than this node. Both calls must return true for the tree to be valid.
}
End of the validate helper method.

class Solution {
Defines the Solution class with a private recursive validate helper and a public entry point.
public:
Public access specifier for the LeetCode-required entry point method.
    bool isValidBST(TreeNode* root) {
Public entry point that takes the root of a binary tree and returns true if it is a valid BST. Passes nullptr for both bounds to start with an unrestricted range.
        return validate(root, nullptr, nullptr);
Start validation with null bounds, meaning no constraints. Instead of using numeric infinity (which risks overflow with int), we pass actual ancestor TreeNode pointers and compare values directly.
    }
End of the isValidBST method.
private:
Private access specifier for the recursive helper method.
    bool validate(TreeNode* node, TreeNode* low, TreeNode* high) {
Private recursive helper. Uses TreeNode pointers for bounds instead of integer values — if `low` is null there is no lower bound, if `high` is null there is no upper bound. This elegantly avoids integer overflow issues.
        if (!node) return true;
Base case: null nodes are valid BSTs. Terminates recursion at leaf children.
        if (low && node->val <= low->val) return false;
Check the lower bound: if `low` is not null and the current node's value is less than or equal to the low bound's value, the BST property is violated. Returns false immediately.
        if (high && node->val >= high->val) return false;
Check the upper bound: if `high` is not null and the current node's value is greater than or equal to the high bound's value, the BST property is violated.
        return validate(node->left, low, node) &&
Recurse left with the current node as the new upper bound. All left descendants must be less than this node. Short-circuit `&&` avoids unnecessary right subtree checks.
               validate(node->right, node, high);
Recurse right with the current node as the new lower bound. All right descendants must be greater than this node.
    }
End of the validate helper method.
};
End of the Solution class.