# Use long long int: c++ solution

• ``````class Solution {
public:
bool Valid(TreeNode *rt,long long int low,long long int high){
if(rt==NULL) return true;
if(rt->val<=low || rt->val>=high) return false;
return Valid(rt->left,low,rt->val)&&Valid(rt->right,rt->val,high);
}
bool isValidBST(TreeNode* root) {
return Valid(root,(long long int)INT_MIN-1,(long long int)INT_MAX+1);
}
};``````

• Another solution using Morris Traversal, an iterative one.

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
if(!root) return true;
int cur = 0;
long prev = (long)INT_MIN-1;
bool flag = true; //using flag here to record the status to avoid return too early without restoring the tree which will cause Runtime Error.
while(root)
{
if(!root->left)
{
cur = root->val;
root = root->right;
if(cur <= prev) flag =  false;
prev = cur;
}
else
{
TreeNode* pre = root->left;
while(pre->right && pre->right!=root)
pre = pre->right;
if(!pre->right)
{
pre->right = root;
root = root->left;
}
else
{
pre->right = NULL;  //restore the tree;
cur = root->val;
root = root->right;
if(cur <= prev) flag = false;
prev = cur;
}
}
}
return flag;
}
};``````

• I was getting an error in 67th test case until i used long long int can you please explain the use of it ?

• Because, in that case, the minimum node has value INT_MIN. Using this method, we want the lower bound be less than the minimum node. A proper choice is we pick low=INT_MIN-1. Using int, this number is overflowed, therefore, we need to use long long int. (sry for my poor English)

• Okay, that makes sense, but my code without the long long int didn't work for the 67th test case which had input as [2,1,4,7,4,8,3,6,4,7].
I don't see any input being overflowed in this case.
Here is the link to the code. https://leetcode.com/discuss/109877/easy-16ms-c-solution
If you removed long long int from it, it wouldnt work for the above test. Can you please point ou the mistake.

• I remove the "long long int" and run the test. It fails at 67th test, but the input is
"Input:
[2147483647]"
That is INT_MAX, one number.
It is not [2,1,4,7,4,8,3,6,4,7] :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.