A program to check if a binary tree is BST or not | GeeksforGeeks
METHOD 3 (Correct and Efficient) O(n)
The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.
METHOD 3 (Correct and Efficient) O(n)
The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.
intisBST(structnode* node){return(isBSTUtil(node, INT_MIN, INT_MAX));}intisBSTUtil(structnode* node,intmin,intmax){/* an empty tree is BST */if(node==NULL)return1;/* false if this node violates the min/max constraint */if(node->data < min || node->data > max)return0;/* otherwise check the subtrees recursively,tightening the min or max constraint */returnisBSTUtil(node->left, min, node->data-1) &&// Allow only distinct valuesisBSTUtil(node->right, node->data+1, max);// Allow only distinct values}
METHOD 4(Using In-Order Traversal)
1) Do In-Order Traversal of the given tree and store the result in a temp array.
3) Check if the temp array is sorted in ascending order, if it is, then the tree is BST.
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST.
The use of static variable can also be avoided by using reference to prev node as a parameter (Similar to this post).
boolisBST(structnode* root){staticstructnode *prev = NULL;// traverse the tree in inorder fashion and keep track of prev nodeif(root){if(!isBST(root->left))returnfalse;// Allows only distinct valued nodesif(prev != NULL && root->data <= prev->data)returnfalse;prev = root;returnisBST(root->right);}returntrue;}
METHOD 2 (Correct but not efficient)
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.
int isBST(struct node* node) { if (node == NULL) return(true); /* false if the max of the left is > than us */ if (node->left!=NULL && maxValue(node->left) > node->data) return(false); /* false if the min of the right is <= than us */ if (node->right!=NULL && minValue(node->right) < node->data) return(false); /* false if, recursively, the left or right is not a BST */ if (!isBST(node->left) || !isBST(node->right)) return(false); /* passing all that, it's a BST */ return(true); }Read full article from A program to check if a binary tree is BST or not | GeeksforGeeks
