Friday, January 13, 2017

Check if a binary tree is a binary search tree

/*   struct Node {
      int data;
      Node* left;
      Node* right;
   }
*/
bool checkBST_util(Node * root, int min, int max) {
    bool ret=true;
    if (root == NULL) return true;
    if (root->left) {
          if (root->data > root->left->data && root->left->data<max && root->left->data>min)
            ret =true;
          else
              return false;
    }
    if (root->right) {
          if (root->data < root->right->data && root->right->data < max && root->right->data > min)
            ret =true;
          else
              return false;
    }
    return (ret && checkBST_util(root->left, min, root->data < max ? root->data : max) && checkBST_util(root->right, root->data>min ? root->data:min , max));
}
bool checkBST(Node* root) {
       return checkBST_util(root, -1, 100000); 
}

No comments:

Post a Comment