Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as a binary tree in which the value of each node has all values to the left of the node less than the node's value and all values to the right of the node greater than the node's value.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= Node.val <= 10^4
Examples:
Input: [2,1,3]
Output: true
Explanation: The tree has a root node with value 2, a left child with value 1, and a right child with value 3. This satisfies the BST property.
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The tree has a root node with value 5, a left child with value 1, and a right child with value 4. The right child of the root node has a value 3, which is less than the root node's value, violating the BST property.
Solutions
In-Order Traversal
This solution uses in-order traversal to visit the nodes in ascending order. It keeps track of the previous node's value and checks if the current node's value is greater than the previous one. If not, it returns false. Otherwise, it continues the traversal.
class Solution {
public: bool isValidBST(TreeNode* root) {
long long prev = LLONG_MIN;
return inOrder(root, prev);
}
private: bool inOrder(TreeNode* node, long long& prev) {
if (!node) return true;
if (!inOrder(node->left, prev)) return false;
if (node->val <= prev) return false;
prev = node->val;
return inOrder(node->right, prev);
}
}
;Follow-up:
How would you optimize the solution to use less space?
