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 http://en.wikipedia.org/wiki/Binary_search_tree 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