Check if a binary tree is a binary search tree in O(n)

Method 1 of previous post runs slowly since it traverses over some parts of the tree many times.As we stated in previous post that all left nodes must be less than or equal to current node, which must be less than all the right nodes.

Keeping this in mind, we can approach the problem by passing down the min and max values.As we iterate through the tree , we verify against progressively narrower ranges.

bool isBST(struct node* root)
{
	return isBSTHelper(root,INT_MIN,INT_MAX);
}

bool isBSTHelper(struct node* root,int min,int max)
{
	if(root==NULL)
		return true;

	if(n->data<=min || n->data > max)
		return false;

	if(!isBSTHelper(root->left,min,n->data) ||
			!isBSTHelper(root->right,n->data,max))
	{
		return false;
	}
	return true;
}

Time Complexity for this solution is O(N), where N is the number of nodes in the tree. This is the best possible time, since any algorithm must visit all its nodes.

3 Thoughts on “Check if a binary tree is a binary search tree in O(n)

  1. i think line 9 should read return true

  2. Rajiur Rahman on September 18, 2015 at 1:58 am said:

    We can find the min and max of the tree very easily. Thanks for your solution.
    :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation