L46. Check if a tree is a BST or BT | Validate a BST

#treeSeries #striver #placements

[takeUforward]

Please do like the video, and let me know in the comments, did you understand?

[harshmittal]

Another approach to this question could be to use inorder traversal and make sure it is strictly increasing . For the inorder traversal we could use morris traversal so that no auxillary stack space is used which in case of recursion would have been O(n) .
The code is below:

bool isValidBST(TreeNode* root) {
bool b=true;
bool first=true;
int prev;
TreeNode* curr=root;
while(curr){
if(curr->left==NULL){
if(first){
prev=curr->val;
first=false;
}
else{
if(curr->val<=prev){
b=false;

}
else{
prev=curr->val;
}
}
curr=curr->right;
}else{
TreeNode* tmp=curr->left;
while(tmp->right && tmp->right!=curr){
tmp=tmp->right;
}
if(tmp->right==NULL){
tmp->right=curr;
curr=curr->left;
}
else{
if(curr->val<=prev){
b=false;

}
else{
prev=curr->val;
}
tmp->right=NULL;
curr=curr->right;
}
}
}
if(b)
return true;
return false;
}

[tulika]

Happy to see that you are back with videos on TUF. TUF is ❤️. This tree series has helped me a lot in one of my recent interview.

[akashpurbia]

My Solution:
Intuition:
We can simply use inorder traversal because if the given BT is BST then the inorder traversal will be in sorter order, and we check this whenever we visit a node. If we find that the any single node’s value is not increased from the last value then we can say that the tree is not BST.

class Solution
{
public:
//Function to check whether a Binary Tree is BST or not.
int temp = INT_MIN;
void Inorder(Node *root, bool &flag)
{
if(!root) return;

Inorder(root->left, flag);

if(temp<root->data)
temp = root->data;
else
flag = false;

Inorder(root->right, flag);
}
bool isBST(Node* root)
{
// Your code here
bool flag = true;
Inorder(root, flag);
return flag;
}
};

[noobcoder]

we can also do a inorder traversal, taking a current varaible, where we can check if my curren value is greater than the stored value

[ajaykarthik]

My approach was, perform inorder and check wheather it is in increasing order or not

[aasheesh]

We can also use Inorder because Inorder of BST is sorted. so we can just do inorder transversal and use a previous pointer which track previous number. Here is my code:
public boolean isValidBST(TreeNode root) {
inorder(root);
return flag;
}
boolean flag = true;
long prev = Long.MIN_VALUE;
private void inorder(TreeNode root) {
if(root == null) return;
inorder(root.left);
if(prev >= root.val){
flag = false;
return;
}
else prev = root.val;
inorder(root.right );
}

[subhajitdey]

My first intuition was to check whether for every node the left_max(max of nodes on the left) and right_min(min of nodes on the right), left_max<node->data<right_min, but it was hard to implement . Hope I can implement this logic after sometime:)

[shivakumarranade]

Greatt explanation!!. But actually we can also perform an inorder traversal as it will give sorted order and store it in a vector or something. Then iterate through the vector and if (i+1)th node is lesser than (i)th node then return false or true.

[tanaykamath]

One can also solve this using inorder traversal, without needing to store it in an array!
like this:

class Solution {
long prev;

public boolean isValidBST(TreeNode root) {
prev=Long.MIN_VALUE;


if(root.val==Long.MIN_VALUE || root.val==Long.MAX_VALUE){
return false;
}

return inorderCheck(root);
}

boolean inorderCheck(TreeNode node){
if(node==null){
return true;
}

boolean

if(!flag){
return false;
}


if(prev>=node.val){
return false;
}else{
prev=node.val;
}




return flag;
}

}

[sanjubaloria]

Sir you nailed the tree series.Never find such kind of tree series before

[shreyasvishwakarma]

I think one added Solution is : Take the inorder of given BST ( why ? INOREDER OF BST is ALWAYS SORTED) . Check if it is sorted or not . If sorted return "YES" else "NO"
Time Complexity : O(n)
Space Complexity : O(n) --> We are using extra space to store node values

[av]

you made it really simpler, it was indeed a tough one. your choice of test case also explains the concept really well.

[LokeshSharma-hmjz]

i was confident about my code, and then this test case appears.. Thanks

[soumyodeepdey]

Another approach can be verifying whetehr the inorder traversal of the tree yields a sorted arrray or not. But it would require two traverSALS. ONE TO CONSTRUCT THE INORDER TRAV AND THEN TO traverse the array to check for sorted or not. So TC is O(2n). Also need an extra space of O(n) for the inorder array. Suboptimal.

[akshat_]

Thanks man for this amazing explanation.
It is a great method to use concept of upper and lower bound.

[shwetanknaveen]

Code using int max, min parameters-->

class Solution {
public:
bool recHelper(TreeNode* root, int max, int min)
{
if(!root)//empty node doesn't violate BST property
return true;

if(root->val>max || root->val<min)//if root value is greater than max value or less than min value then
return violates BST property hence return false

if(root->val==INT_MIN)//if node value is INT_MIN
{
if(root->left) return false;//We can't go left as we can't afford value less than INT_MIN
else return recHelper(root->right, max, root->val+1);//if there is no left child then we can go usual way to right

//We can't leave this else case for default case otherwise there, while checking for left subtree, it will try
//to store INT_MIN-1 in int which will cause overflow
}

if(root->val==INT_MAX)//if node value is INT_MAX
{
if(root->right) return false;//We can't go right as we can't afford value greater than INT_MAX
else return recHelper(root->left, root->val-1, min);//if there is no right child then we can go usual way to left


//We can't leave this else case for default case otherwise there, while checking for right subtree, it will try
//to store INT_MAX+1 in int which will cause overflow
}

return recHelper(root->left, root->val-1, min) && recHelper(root->right, max, root->val+1);
//The default case to check both subtrees for BST property
}
bool isValidBST(TreeNode* root) {
return recHelper(root, INT_MAX, INT_MIN);//initially max value can be INT_MAX and min value can be INT_MIN
}
};

[uniquematrixhc]

i watched your video for 1:48 & got my solution thanks

[ankitduttavlogs]

what about inorder traversal and checking current value with previous value ?? TC - O(n) for worst, SC - O(1)

[krishnaradhey]

Another approach can be to traverse via morris traversal without using any memory
and maintaining pre_count and current_count to check if current value is greater than previous one,
We have to maintain INT_MIN case here
CODE:-

class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root->left== nullptr && root->right==nullptr)return true;
int pre = INT_MIN;
int aim = 0;
bool cond = true;
while(root)
{
if(!root->left)
{
if(pre == INT_MIN && root->val == INT_MIN && aim == 0)
{
aim++;
}
else if(root->val <= pre)cond= false;
pre = root->val;
root = root->right;
}
else if(root->left)
{
TreeNode * prev = root->left;
while(prev->right != nullptr && prev->right != root)
{
prev = prev->right;
}
if(!prev->right )
{
prev->right = root;
root=root->left;
}
else if(prev->right ==root)
{
prev->right = nullptr;
if(root->val <= pre)cond = false;
pre = root->val;
root = root->right;
}
}
}
return cond;
}
};
DO LIKE THIS COMMENT