Sai Charan

The following code tests if the input binary tree is, in fact, a Binary Search Tree. This was as terse as I could get it. Any got more terse code? Suggestions/comments welcome.

bool IsBST(TreeNode* node){
	if( !node ) return true;// trivially true.
	if( node->left )
		if( node->left->val > node->val ) return false; //fail early
	if( node->right )
		if( node->right->val < node->val ) return false; //fail early

	return ( IsBST(node->left) && IsBST(node->right) ); //recursively test subtrees
}

Update: Notice the tail recursion? Its super-efficient!
Update-update: Thanks to Kartik (see comments below) for pointing out that the last line is NOT tail-recursive.
Yet another update: The algorithm is does NOT check for IsBST(). The criterion of root being greater than all right children and smaller than left children is not always checked. See http://en.wikipedia.org/wiki/Binary_search_tree for more details.

---

Tags  ·   algorithm  ·   Show Comments ▾