Write a function to check if a binary tree is a binary search tree

Binary search tree’s Properties :

1. root value is greater than or equal to maximum value in left sub tree.
2. root value is less than minimum value in right sub tree.
3. In Order traversal of BST produces a sorted array.

Based on above properties we can check if a binary tree is a binary search tree or not.

Method 1: Using properties 1 & 2.

int minValue(struct node* node)
{
    struct node* x = node;
    while(x->left!=NULL)
        x=x->left;
    return x->data;
}

int maxValue(struct node *node)
{
    struct node* x = node;
    while(x->right!=NULL)
        x=x->right;
    return x->data;
}
bool isBST(struct node* root)
{
    if (root==NULL)
        return(true);
    if (root->left!=NULL && maxValue(root->left) > root->data)
       return(false);
    if (root->right!=NULL && minValue(root->right) <= root->data)
       return(false);
    if (!isBST(root->left) || !isBST(root->right))
       return(false);

    return(true);
}

Time complexity : O(N)
Method 2 : Using property 3. Do an in-order traversal of tree, copy the elements to an array and then check if the array is sorted.

void copyBST(struct node *root,int arr[])
{
 static int index = 0;
 if(root==NULL)
    return;
 copyBST(root->left,arr);
 arr[index] = root->data;
 index++;
 copyBST(root->right,arr);
}

bool isBST(struct node* root)
{
  int size = count(root);
  /*check http://wp.me/p3FSTj-3Z for count function implementation */
 int arr[size];
 copyBST(root,arr);
 for(int i = 1;i <size;i++)
 {
   if(arr[i] < arr[i-1])
    return false;
 }
 return true;

}

Time Complexity : O(N)

3 Thoughts on “Write a function to check if a binary tree is a binary search tree

  1. Amit Gaur on July 4, 2013 at 12:09 am said:

    Can you elaborate for 1st method how can be time complexity is O(N)?

  2. Pingback: Check if Binary tree is binary search tree or not O(n) | CrazyforCode

  3. crazyadmin on July 4, 2013 at 11:27 pm said:

    Amit,

    For this problem recurrence would be T(n) = 2T(n/2)+2log(n/2)
    O(logn) is the average case time complexity of find minValue or maxValue function.Since here we are applying it on left subtree and right subtree so log(n/2). Using master theorem we can calculate the time complexity which would come out O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation