## # 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);
}
};
``````