Wednesday 19 October 2016

Is This a Binary Search Tree? (CTCI)

Problem: Is This a Binary Search Tree?
Given the root node of a binary tree, check if it's also a binary search tree?

bool checkBST(Node* root) {
      int increasing = -1;
      return inorderTraverse(&increasing, root);
   }
    
    bool inorderTraverse(int *incr, Node *root)
    {
       if(root==NULL) return true;
       bool ret = inorderTraverse(incr, root->left);
        if(*incr>=root->data) return false;
        *incr = root->data;
       ret = ret & inorderTraverse(incr, root->right); 
       return ret;
    }

No comments:

Post a Comment