If you want to check if a given Binary Tree is BST or not? If current key value is greater, then continue, else return false. See the below example to check if a given Binary Tree is BST or not.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <stdio.h> #include <stdlib.h> #include <limits.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; int isBSTUtil(struct node* node, int min, int max); /* Returns true if the given tree is a binary search tree (efficient version). */ int isBST(struct node* node) { return(isBSTUtil(node, INT_MIN, INT_MAX)); } /* Returns true if the given tree is a BST and its values are >= min and <= max. */ int isBSTUtil(struct node* node, int min, int max) { /* an empty tree is BST */ if (node==NULL) return 1; /* false if this node violates the min/max constraint */ if (node->data < min || node->data > max) return 0; /* otherwise check the subtrees recursively, tightening the min or max constraint */ return isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values isBSTUtil(node->right, node->data+1, max); // Allow only distinct values } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /* Driver program to test above functions*/ int main() { struct node *root = newNode(4); root->left = newNode(2); root->right = newNode(5); root->left->left = newNode(1); root->left->right = newNode(3); if(isBST(root)) printf("Is BST"); else printf("Not a BST"); getchar(); return 0; } |
If you like this question & answer and want to contribute, then write your question & answer and email to freewebmentor[@]gmail.com. Your question and answer will appear on FreeWebMentor.com and help other developers.
