Validate Binary Search Tree
Given the root of a binary tree, determine whether it is a valid binary search tree: for every node, all values in the left subtree are strictly less and all values in the right subtree are strictly greater than the node's value.
Constraints:
- The number of nodes is in the range
[1, 10^4]. -2^31 <= Node.val <= 2^31 - 1
Intuition
1 52 / \3 1 44 / \5 3 6This tree is not a BST, even though every node is bigger than its left child and smaller than its right child. Node 3 sits in the right subtree of 5, but 3 is smaller than 5.
So checking a node only against its direct children is not enough. Every node must fit inside a range set by all of its ancestors.
Approach: Pass Down an Allowed Range
Each node carries an allowed open interval (low, high).
- The root may take any value, so start with
(-infinity, +infinity). - A node is valid only if
low < node.val < high. Otherwise return false. - Going left, the new upper bound becomes the node's value:
(low, node.val). - Going right, the new lower bound becomes the node's value:
(node.val, high). - A
nullnode is valid.
The bounds must be wider than 32-bit integers (use long in C++ and Java), because node values can equal INT_MIN or INT_MAX.
An alternative is to do an inorder traversal and check that the values are strictly increasing.
Code
class Solution {bool check(TreeNode* node, long long low, long long high) {if (node == nullptr) return true;if (node->val <= low || node->val >= high) return false;return check(node->left, low, node->val) &&check(node->right, node->val, high);}public:bool isValidBST(TreeNode* root) {return check(root, LLONG_MIN, LLONG_MAX);}};
Complexity
Each node is checked once.
Recursion stack depth equals the tree height.