Given the root of a binary tree, return true if it is a valid binary search tree. In a valid BST, every value in a node's left subtree is strictly smaller than the node, every value in its right subtree is strictly larger, and both subtrees are valid BSTs themselves.
- The number of nodes is in the range 1 to 10^4
- -2^31 <= Node.val <= 2^31 - 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force, for every node, scans its whole left subtree for the maximum and its right subtree for the minimum, which is O(n^2). The real rule is that every node must lie inside a range set by all its ancestors, not just its parent. So we carry that range down: the root may be anything, a left child must be below its parent, and a right child above it, while also respecting every bound inherited from higher up. Each node is checked once against its range, giving O(n). Equivalently, an inorder traversal of a valid BST is strictly increasing.
Algorithm
- Define
valid(node, low, high). A null node is valid. - If
node.val <= lowornode.val >= high, returnfalse. - Return
valid(node.left, low, node.val) and valid(node.right, node.val, high). - Start with
valid(root, -infinity, +infinity).
O(n)Space: O(h) recursion depthInteger.MIN_VALUE or Integer.MAX_VALUE, so in Java and C++ use long bounds (or nullable bounds) instead of int sentinels, otherwise [2147483647] is wrongly rejected.class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: def valid(node, low, high): # every value in this subtree must lie strictly between low and high if not node: return True if node.val <= low or node.val >= high: return False return valid(node.left, low, node.val) and valid(node.right, node.val, high)Β return valid(root, float("-inf"), float("inf"))