Domain 2MediumCORE

Validate Binary Search Tree

We are given the root of a binary tree and need to validate if it adheres to Binary Search Tree (BST) properties. A valid BST requires: 1. Left Subtree: All nodes must be strictly less than the current node's value (node.val). 2. Right Subtree: All nodes must be strictly greater than the current node's value (node.val). 3. Recursive Property: Both left and right subtrees themselves must also be valid BSTs.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

98. Validate Binary Search Tree

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 28.9%


Problem Breakdown

We are given the root of a binary tree and need to validate if it adheres to Binary Search Tree (BST) properties. A valid BST requires:

  1. Left Subtree: All nodes must be strictly less than the current node’s value (node.val).
  2. Right Subtree: All nodes must be strictly greater than the current node’s value (node.val).
  3. Recursive Property: Both left and right subtrees themselves must also be valid BSTs.

Key Constraints & Tricky Cases:

  • Strict Inequality: Duplicates are not allowed (e.g., 5 cannot have a child with value 5). If the problem allows duplicates, it would specify “less than or equal” for one side and strictly greater for the other; here we assume strict inequality based on standard BST definitions.
  • Global vs Local Constraints: A naive check comparing only immediate children (left.val < parent) is insufficient because a node deep in the right subtree must still be greater than all ancestors, not just its direct parent. For example, if root is 5, and we go left to -10 then right to 4, that 4 violates the BST property relative to root 5.
  • Input Range: Node values fit within standard 32-bit integers (Python handles this natively). Tree size up to 10410^4 nodes.

Intuition

The first instinct is often a simple DFS traversal checking if left.val < current and right.val > current. However, as noted in the breakdown, this fails because it doesn’t track constraints propagated from ancestors.

Why Brute Force Fails: Checking only immediate children allows invalid values deep within subtrees (e.g., value -100 is valid relative to a parent of -5, but invalid if an ancestor was 0).

Key Insight: Every node in the tree has an implicit range (min_val, max_val) it must satisfy based on its path from the root.

  • When traversing left, we tighten the upper bound: new max becomes current node.val.
  • When traversing right, we tighten the lower bound: new min becomes current node.val.

We can pass these bounds down recursively (or iteratively) to validate every node against its valid range.

Approach

  1. Define a helper function that takes (root, min_val, max_val) as arguments.
  2. Base Case: If the current node is None, return True (empty subtree satisfies BST property).
  3. Validation Check: Verify if node.val lies strictly within (min_val, max_val). If not (<= min_val or >= max_val), return False.
  4. Recursive Step:
    • Recurse on the left child with bounds: (min_val, node.val) (upper bound tightens).
    • Recurse on the right child with bounds: (node.val, max_val) (lower bound tightens).
  5. Return True only if both recursive calls return True.

Complexity Analysis

  • Time: O(N)O(N) where NN is the number of nodes. We visit every node exactly once in a single DFS traversal.
  • Space: O(H)O(H) for recursion stack space, where HH is the height of the tree. In a balanced tree, this is O(log⁡N)O(\log N). In a skewed (linked-list-like) tree, it degrades to O(N)O(N).

Solution

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        # Helper function to traverse with bounds (min_val, max_val) exclusive.
        # Using float('-inf') and 'inf' handles the initial full range safely 
        # without needing a sentinel node value check for min/max logic initially.
        def validate(node, low, high):
            if not node:
                return True
            
            # If current node violates bounds relative to ancestors, fail immediately
            if not (low < node.val < high):
                return False
            
            # Recurse left with upper bound tightened by current node value
            # Recurse right with lower bound tightened by current node value
            return validate(node.left, low, node.val) and \
                   validate(node.right, node.val, high)

        if not root:
            return True
        
        return validate(root, float('-inf'), float('inf'))

Edge Cases Handled

  • Empty Tree: The initial check if not root handles a null input gracefully (though constraints specify N≥1N \ge 1, robustness is good).
  • Single Node: Returns True as the range (min, max) allows any value for the single node.
  • Duplicate Values: Strict inequality (<) ensures duplicates are rejected immediately upon encountering them in a subtree where they violate an ancestor’s constraint or direct parent comparison.
  • Negative Numbers: Python integers handle negative values correctly; float('-inf') works as expected with negatives (e.g., -10 < -5).
  • Skewed Trees: While recursion depth could hit limits in production environments (N=104N=10^4 skewed), this solution uses the standard recursive pattern accepted for LeetCode. In a real-world scenario, an iterative stack-based approach would be used to avoid RecursionError.