2. Check BST 2 #

Created Friday 07 February 2020

• We need to decrease our work. Let us calculate the min and max in one go. Remember have the height parameter as well.
• Basically at every node, we are okay if the left is a BST and that it’s maximum is less than root->data and the right subtrees’s minimum is greater than(or equal to if duplicates are allowed).
• When we return isBST, we may also return the max for the left subtree and min for the right subtree. This selective behavior will still require two functions, which we already use. Better if we return all three of min, max and isBST.

**Bottom Up Approach - we need to return multiple things, recursion only takes us down. **

• we use pairs
• Code:

pair<pair<int, int>, bool> isBST(BT*)
{
	pair<pair<int, int>, bool> ret;
	ret.first.first = INT_MIN;
	ret.first.second = INT_MAX;
	ret.second = false;
	if(root==NULL)
	{
		ret.second = true;
		return ret;
	}
	if(root->left==NULL && root->right==NULL)
	{
		ret.first.first = root->data;	// minimum and maximum are the same
		ret.first.second = root->data;
		ret.second = true;
		return ret;
	}
	if(root->left!=NULL)
		ret = isBST(root->left);
	if(ret.second) // we are only worried about the minimum
	{
		pair<pair<int, int>, bool> ret2;
			ret2 = isBST(root->right);
			ret.first.second = ret2.second.second; // maximum
			ret.second &&= re2.second;
			return ret;
	}
}

Time complexity: T(n) = 2T(n/2) + k, O(n) is independent of height.