Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
A binary search tree (BST) has the following properties.
• The left subtree of a node contains only nodes with keys less than the root node’s key.
• The right subtree of a node contains only nodes with keys greater than the root node’s key.
• Both the left and right subtrees must also be binary search trees.
From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.
Using Inorder Traversal
vector<int> v;
void inOrder(Node *t)
{
if (t == NULL)
{
return;
}
inOrder(t->left);
v.push_back(t->data);
inOrder(t->right);
}
bool checkBST(Node *root)
{
inOrder(root);
bool res = true;
for (int i = 0; i < v.size() - 1; i++)
{
if (v[i + 1] <= v[i])
{
res = false;
break;
}
}
return res;
}
class Solution
{
public:
bool isValidBST(TreeNode *root)
{
if(root == NULL){return true;}
if(root->left==NULL && root->right==NULL){return true;}
stack<TreeNode *> s;
TreeNode *t = root;
int prev = INT_MIN;
bool res = true;
vector<int> v;
while (t != NULL || !s.empty())
{
if (t != NULL)
{
s.push(t);
t = t->left;
}
else
{
t = s.top();
v.push_back(t->val);
s.pop();
t = t->right;
}
}
for(int i=0;i<v.size()-1;i++){
if(v[i+1]<=v[i]){
res = false;
break;
}
}
return res;
}
};
Time Complexity O(n) and Space Complexity O(n). This solution uses an extra space complexity of O(n)
Solution II
class Solution
{
public:
bool isValidBST(TreeNode *root)
{
stack<TreeNode *> s;
TreeNode *t = root;
int prev = INT_MIN;
bool res = true;
while (t != NULL || !s.empty())
{
if (t != NULL)
{
s.push(t);
t = t->left;
}
else
{
t = s.top();
if (t->val > prev)
{
prev = t->val;
}
else
{
res = false;
break;
}
s.pop();
t = t->right;
}
}
return res;
}
};
In this solution, if we check while doing inorder traversal we have an edge case if the tree has INT_MIN as one of its nodes it can create the error.
