fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* A binary tree node has data, pointer to
  5. left child and a pointer to right child */
  6. struct Node {
  7.     int data;
  8.     struct Node *left, *right;
  9.  
  10.     Node(int data)
  11.     {
  12.         this->data = data;
  13.         left = right = NULL;
  14.     }
  15. };
  16.  
  17. bool isBSTUtil(struct Node* root, Node*& prev)
  18. {
  19. 	if (root) cout << "root: " << root->data;
  20. 	if (prev) cout << " prev: " << prev->data;
  21. 	cout << endl;
  22.     // traverse the tree in inorder fashion and
  23.     // keep track of prev node
  24.     if (root) {
  25.         if (!isBSTUtil(root->left, prev))
  26.             return false;
  27.  
  28.         // Allows only distinct valued nodes
  29.         if (prev != NULL && root->data <= prev->data)
  30.             return false;
  31.  
  32.         prev = root;
  33.  
  34.         return isBSTUtil(root->right, prev);
  35.     }
  36.  
  37.     return true;
  38. }
  39.  
  40. bool isBSTUtil2(Node* root) {
  41. 	if (root == nullptr) {
  42. 		return true;
  43. 	}
  44. 	if (!isBSTUtil2(root->left)) {
  45. 		return false;
  46. 	}
  47. 	if (!isBSTUtil2(root->right)) {
  48. 		return false;
  49. 	}
  50. 	bool result = true;
  51. 	if (root->left != nullptr) {
  52. 		result = result && (root->data > root->left->data);
  53. 	}
  54. 	if (root->right != nullptr) {
  55. 		result = result && (root->data < root->right->data);
  56. 	}
  57. 	return result;
  58. }
  59.  
  60. bool isBST(Node* root)
  61. {
  62.     // Node* prev = NULL;
  63.     // return isBSTUtil(root, prev);
  64.  
  65. 	return isBSTUtil2(root);
  66. }
  67.  
  68. /* Driver code*/
  69. int main()
  70. {
  71.     struct Node* root = new Node(7);
  72.     root->left = new Node(3);
  73.     root->right = new Node(10);
  74.     root->right->left = new Node(8);
  75.     root->right->right = new Node(15);
  76.  
  77.     // Function call
  78.     if (isBST(root))
  79.         cout << "Is BST";
  80.     else
  81.         cout << "Not a BST";
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Is BST
https://ideone.com/muxj9a
language:
C++ (gcc 8.3)
created:
106 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!