fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. bool isBSTUtil(const vector<int>& preorder, int& index, int minValue, int maxValue) {
  7.     // Base case: If index reaches the size of preorder, return true
  8.     if (index >= preorder.size()) return true;
  9.  
  10.     // Get the current value and check if it is within the allowed range (BST property)
  11.     int currentVal = preorder[index];
  12.     if (currentVal < minValue || currentVal > maxValue) return false;
  13.  
  14.     // Move to the next value
  15.     index++;
  16.  
  17.     // Recursively check the left and right subtree
  18.     // For the left subtree, the allowed range is (minValue, currentVal)
  19.     bool leftValid = isBSTUtil(preorder, index, minValue, currentVal);
  20.  
  21.     // For the right subtree, the allowed range is (currentVal, maxValue)
  22.     bool rightValid = isBSTUtil(preorder, index, currentVal, maxValue);
  23.  
  24.     return leftValid && rightValid;
  25. }
  26.  
  27. bool isBST(const vector<int>& preorder) {
  28.     int index = 0;
  29.     return isBSTUtil(preorder, index, INT_MIN, INT_MAX);
  30. }
  31.  
  32. int main() {
  33.     vector<int> preorder = {2 , 1 , 3 , 4 , 5};  // Example pre-order traversal
  34.  
  35.     if (isBST(preorder))
  36.         cout << "The given pre-order traversal is a BST" << endl;
  37.     else
  38.         cout << "The given pre-order traversal is not a BST" << endl;
  39.  
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
2 1
stdout
copy 
The given pre-order traversal is not a BST
https://ideone.com/HNOxEp
language:
C++14 (gcc 8.3)
created:
6 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!