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)
Can you elaborate for 1st method how can be time complexity is O(N)?
Pingback: Check if Binary tree is binary search tree or not O(n) | CrazyforCode
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).