# BST or not? (most optimized)

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!

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 . 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

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

@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 .