💬 Discord
Sign In
NeetCode #442LC-98MediumTreesBlind 75NC 150NC 250
← Back to All Problems

#442 · #98 · Validate Binary Search Tree(验证二叉搜索树)

📌 Problem Statement & Constraints

Given the root of a binary tree, determine whether it is a valid binary search tree: every node's value must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree. Constraints: the number of nodes is in [1, 10^4], -2^31 <= Node.val <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Checking only that each node's value lies between its immediate children is insufficient -- a violation can occur several levels deep.
  2. Carry the allowed open interval (lo, hi) down the recursion.
  3. Going left tightens hi to the current value; going right tightens lo.
  4. A node is valid when lo < node.val < hi. The initial interval is (-infinity, +infinity).

💻 Benchmark Python3 Implementation

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check(node: Optional[TreeNode], lo: float, hi: float) -> bool:
            if not node:
                return True
            if not (lo < node.val < hi):   # outside the allowed open interval
                return False
            return (check(node.left, lo, node.val)
                    and check(node.right, node.val, hi))

        return check(root, float("-inf"), float("inf"))


# In-order variant: the traversal must be strictly increasing
class Solution2:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float("-inf")

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= prev:           # not strictly increasing
                return False
            prev = node.val
            return inorder(node.right)

        return inorder(root)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Only comparing a node with its immediate children: [10, 5, 15, null, null, 6, 20] passes that test but is invalid, because 6 is in the right subtree of 10. The interval approach catches it.
  • Using closed intervals lo <= node.val <= hi: duplicate values are not allowed, so the bounds must be strict.
  • Initialising the interval with float('-inf')/float('inf'): correct, and safe even for 32-bit extreme values. Using -231 and 231 - 1 as bounds would break for a node with exactly those values.
  • Comparing with the previous node in a pre-order traversal: only the in-order traversal gives the sorted order.