Check if tree is a BST O(n) code Common Interview Question

Check if tree is a Binary Search Tree or not 

Most Common Interview Question

Problem Statement

Write a program to check if a tree is a Binary Search Tree or not.

Algorithm

While doing in-order traversal, keep track of previous node in a static variable and compare its data with root's (next) data. Plus also check if left subtree and right subtree also follow binary search tree property.

If you have a different approach in mind, please share it in comments section for our readers.

Solution

int isBST(node *root) {

    static int node *prev_node = NULL;
   
    if(root == NULL) return 1;
   
    if(!isBST(root->left))
        return 0;
       
    if(prev_node != NULL && root->data <= prev_node->data)
        return 0;
    prev_node = root;
   
    if(!isBST(root->right))
        return 0;
    
    return 1;       
    
}

Time Complexity

O(n) since we visit each node only once.


If you find this blog somewhat helpful, please give a +1.