Binary Search Tree
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. |