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

## No comments:

## Post a Comment