Check for BST

Given a binary tree. Check whether it is a BST or not.
Note: We are considering that BSTs can not contain duplicate Nodes.

Example 1:

Input:
    2
 /    \
1      3
Output: 1 
Explanation: 
The left subtree of root node contains node 
with key lesser than the root node’s key and 
the right subtree of root node contains node 
with key greater than the root node’s key.
Hence, the tree is a BST.

Example 2:

Input:
  2
   \
    7
     \
      6
       \
        5
         \
          9
           \
            2
             \
              6
Output: 0 
Explanation: 
Since the node with value 7 has right subtree 
nodes with keys less than 7, this is not a BST. 




method  :

c++ implementation:

vector<int>v;
void printInorder(struct Node* node) 
{  
    if (node == NULL) 
        return; 

    printInorder(node->left); 
  
    v.push_back(node->data); 
  
    printInorder(node->right); 
} 
bool isBST(Node* root) 
{
   int c=-1;
    
    vector<int>::iterator i;
    printInorder(root);
for(i=v.begin();i!=v.end();i++)
{ 
    if(*i<=c)
    return false;
    else
    c=*i;
} 
return true;
}



Time Complexity: O(n) 

space Complexity: O(n)  

darkmode