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.

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

  1. Habula on August 19, 2013 at 1:10 am said:

    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.
    :)

  3. Savitha on October 12, 2016 at 8:42 am said:

    Hi,

    Here is question is findout whether the tree is BST or not. We can find out the min (which is the leftmost node in the tree), max (which is the rightmost) node in the tree.

    Are we going with an assumption that we already have BST? Even though all the nodes are greater than or equal to min and lesser than or equal to max, tree might not be a BST.

Leave a Reply to Savitha Cancel 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