BST or not? (most optimized)

Question:
https://practice.geeksforgeeks.org/problems/check-for-bst/1

My approach:

bool flag=true;
int check=INT_MIN;
void checker(Node *root)
{
    if(root)
    {
        checker(root->left);
        if(check>root->data)
        {
            flag=false;
            return;
        }
        else
            check=root->data;
        checker(root->right);
    }
}
bool isBST(Node* root)
{
    
    flag=true;
    checker(root);
    return flag;
}

Solution is correct and works for below test case:

2
12 4
2 N 7 N 6 N 5 N 9 N 2 N 6

But it does NOT works for (reversed order of above TC) :

2
2 N 7 N 6 N 5 N 9 N 2 N 6
12 4

Moreover it is working fine for single test cases.

Any help will be appreciated!

@hackraj @ssrivastava990 @rajarshi_basu @alei help

Can you explain your logic in brief? What does check store after the recursive calls?

If there are multiple calls to isBST() you’ll have to initially check inside isBST() as well.

What does your function return for the following tree:

7 3 4

Please find my approach for checking the BST:

bool util(Node* root , int minn , int maxx)
{
    if(root==NULL)
        return true;
    if(root->data < minn || root->data > maxx)
        return false;
    
    return ((util(root->left,minn,root->data-1)
           && util(root->right , root->data+1 , maxx)));
}

bool isBST(Node* root) {
    return util(root,INT_MIN,INT_MAX);
}

Please let me know if you have any concern.

1 Like

Yes. This seems more like it :sweat_smile:. I’m not able to understand the flow of the posted solution.

I have already mentioned that for individual tc it works fine.
But when multiple cases arise for False to true, it is not giving accurate results! @aneee004
Global variable “check” stores predecessor’s value and check whether the inorder is in ascending order or not!

I wanted to do without min max. Just made changes to original inorder traversal.
My solution works fine for individual tc.
But when multiple TCs arise for False to true, it is not giving accurate results! @csk111165

As I have said.

1 Like

Well yes. I think your logic is solid. Just initially check to INT_MIN between test cases. Otherwise check will store the right bottom node value of the previous test case.

I like your logic! I usually push the in order traversal into a vector, and check if it’s sorted. Nice.

3 Likes

yes i wanted a space optimised version following exactly inorder traversal thing without min max as I want to have only one parameter in function @aneee004
Thank you bro!

1 Like
bool isBST(Node* root, Node* l=NULL, Node* r=NULL) 
{ 
    // Base condition 
    if (root == NULL) 
        return true; 
  
    // if left node exist then check it has 
    // correct data or not i.e. left node's data 
    // should be less than root's data 
    if (l != NULL and root->data <= l->data) 
        return false; 
  
    // if right node exist then check it has 
    // correct data or not i.e. right node's data 
    // should be greater than root's data 
    if (r != NULL and root->data >= r->data) 
        return false; 
  
    // check recursively for every node. 
    return isBST(root->left, l, root) and 
           isBST(root->right, root, r); 
} 

No need to take INT_MIN and INT_MAX

one more suggestion please google first and if still doubt then ask : “https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

Suggestion from my side is you must read all post and follow-up queries. I wanted a method following exactly inorder without min-max thing i.e with only one function parameter. GFG has no such method.

bool isBST(node* root) 
{ 
	static node *prev = NULL; 
	
	// traverse the tree in inorder fashion 
	// and keep track of prev node 
	if (root) 
	{ 
		if (!isBST(root->left)) 
		return false; 

		// Allows only distinct valued nodes 
		if (prev != NULL && 
			root->data <= prev->data) 
		return false; 

		prev = root; 

		return isBST(root->right); 
	} 

	return true; 
} 

This is from GFG , I hope u scroll down next time :slight_smile:

@anee see this -

1 Like

without static variable -

bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
    // traverse the tree in inorder fashion and  
    // keep track of prev node 
    if (root) 
    { 
        if (!isBSTUtil(root->left, prev)) 
          return false; 
   
        // Allows only distinct valued nodes  
        if (prev != NULL && root->data <= prev->data) 
          return false; 
   
        prev = root; 
   
        return isBSTUtil(root->right, prev); 
    } 
   
    return true; 
} 
  
bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

Lol. This is very similar to the posted code. Although static variables in recursion are really confusing (for me).

[EDIT] Not really. This explains it.

1 Like

bro i already mentioned this too that i want in a traditional inorder recursive manner. That type of code is not on GFG…
The one you posted(available on gfg too) is having return type as recursive call. I don’t want this thing.
P.S. I scrolled till bottom only.

My code( as I desired) is working fine with @aneee004 's help!!

No issues , your doubt is cleared then it’s OK .