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.