Advertisement
CSenshi

isBST? V2

Jun 21st, 2019
385
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. /* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.  
  2.  
  3. The Node struct is defined as follows:
  4.     struct Node {
  5.         int data;
  6.         Node* left;
  7.         Node* right;
  8.     }
  9. */
  10.  
  11. #include <limits.h>
  12.  
  13. int find_max(Node* root){
  14.     if (!root)  return INT_MIN;
  15.     int max_right = find_max(root->right);
  16.     int max_left = find_max(root->left);
  17.     return max(max(max_right, max_left), root->data);
  18. }
  19.  
  20. int find_min(Node* root){
  21.     if (!root)  return INT_MAX;
  22.     int min_right = find_min(root->right);
  23.     int min_left = find_min(root->left);
  24.     return min(min(min_right, min_left), root->data);
  25. }
  26.  
  27. bool checkBST(Node* root) {
  28.     if (!root) return true;
  29.    
  30.     if(root->left && find_max(root->left) >= root->data)
  31.         return false;
  32.    
  33.     if(root->right && find_min(root->right) <= root->data)
  34.         return false;
  35.    
  36.    return checkBST(root->right) && checkBST(root->left);    
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement