3. Check BST 3 #

Created Friday 07 February 2020

Better than all this, let us do an even simpler approach: According to the definiton, we can do the following. We can do this very easily. We restrain the left and right restrain. We can code it easily.

Top-down approach. If a node violates the BST principle: It should be on either side of min and max, if not return false;

bool isBST_h(BinaryTreeNode<int>* root, int min, int max)
{
	if(root==NULL)
		return true;
	   // check if the node is okay
	// node's data should be in range of either side of min or max
	if(root->data > min && root->data < max) // only possible scenario
		return isBST_h(root->left, root->data, max) && isBST_h(root->right, min, root->data);
	return false;
}

#include<climits>

bool isBST(BinaryTreeNode<int> *root)
{
	// top down approach
	// simulating the creation if the tree
	if(root==NULL)
		return true;

	// initially we have no restrain
	return isBST_h(root, INT_MAX, INT_MIN); // need to start from -infinity and +infinity`
}

// We did nothing for left and rigtht.

**Insights: **BST is only making the bound for min and max for the left and right subtrees.