# 98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
# Solution
Approach 1: Check that the inorder traversal is monotonically increasing.
Approach 2: Intuitive recursion -- each node in the tree should be bounded by a upper and lower bound given their parents in a BST. Check if each node is in bound.
# Code (Python)
Approach 1:
def isValidBST(self, root: 'TreeNode') -> 'bool':
# inorder traversal is increasing
if not root:
return True
stack = []
node = root
while node:
stack.append(node)
node = node.left
prev = None
while stack:
node = stack.pop()
if prev and prev.val >= node.val:
return False
prev = node
node = node.right
while node:
stack.append(node)
node = node.left
return True
Approach 2:
def isValidBST(self, root: 'TreeNode') -> 'bool':
# recursive with boundaries
return self._helper(root, -float('inf'), float('inf'))
def _helper(self, node, lo, hi):
if not node:
return True
if not lo < node.val < hi:
return False
return self._helper(node.left, lo, node.val) and self._helper(node.right, node.val, hi)
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// Inorder traversal.
// Recursion.
class Solution {
private:
TreeNode *prev = NULL;;
public:
bool isValidBST(TreeNode* root) {
if (root == NULL)
return true;
if (!isValidBST(root->left))
return false;
if (prev && prev->val >= root->val)
return false;
prev = root;
return isValidBST(root->right);
}
};
// Iteration.
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode *curr = root;
TreeNode *prev = NULL;
while (curr || !st.empty())
{
if (curr)
{
st.push(curr);
curr = curr->left;
}
else
{
curr = st.top();
st.pop();
if (prev && prev->val >= curr->val)
return false;
prev = curr;
curr = curr->right;
}
}
return true;
}
};
Approach 2:
// Intuitive recursion.
class Solution {
private:
bool checkIsValidBST(TreeNode *root, int *min, int *max) {
int leftMin = root->val;
int leftMax = root->val;
int rightMin = root->val;
int rightMax = root->val;
if (root->left &&
(!checkIsValidBST(root->left, &leftMin, &leftMax) ||
root->val <= leftMax))
return false;
if (root->right &&
(!checkIsValidBST(root->right, &rightMin, &rightMax) ||
root->val >= rightMin))
return false;
if (min) *min = leftMin;
if (max) *max = rightMax;
return true;
}
public:
bool isValidBST(TreeNode* root) {
if (root == NULL)
return true;
return checkIsValidBST(root, NULL, NULL);
}
};