Binary Search Tree 10 May, 2010 Binary Search Tree

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 for more details.

Tags  ·   algorithm  ·   Show Comments ▾

Original design for Tumblr crafted by Prashanth Kamalakanthan.
Adapted for Tumblr & Jekyll by Sai Charan. Customized theme available on Github.

Sai Charan's blog by Sai Charan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Creative Commons License