Advertisement
i_love_rao_khushboo

Untitled

Sep 3rd, 2022
1,068
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.86 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define mp make_pair
  10. #define F first
  11. #define S second
  12. #define PI 3.1415926535897932384626
  13. #define sz(x) ((int)(x).size())
  14.  
  15. typedef pair<int, int> pii;
  16. typedef pair<ll, ll> pll;
  17. typedef vector<int> vi;
  18. typedef vector<ll> vll;
  19. typedef vector<ull> vull;
  20. typedef vector<bool> vb;
  21. typedef vector<char> vc;
  22. typedef vector<string> vs;
  23. typedef vector<pii> vpii;
  24. typedef vector<pll> vpll;
  25. typedef vector<vi> vvi;
  26. typedef vector<vll> vvll;
  27. typedef vector<vull> vvull;
  28. typedef vector<vb> vvb;
  29. typedef vector<vc> vvc;
  30. typedef vector<vs> vvs;
  31.  
  32. /************************************************** DEBUGGER *******************************************************************************************************/
  33.  
  34. #ifndef ONLINE_JUDGE
  35. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  36. #else
  37. #define debug(x)
  38. #endif
  39.  
  40. void _print(ll t) { cerr << t; }
  41. void _print(int t) { cerr << t; }
  42. void _print(string t) { cerr << t; }
  43. void _print(char t) { cerr << t; }
  44. void _print(ld t) { cerr << t; }
  45. void _print(double t) { cerr << t; }
  46. void _print(ull t) { cerr << t; }
  47.  
  48. template <class T, class V> void _print(pair <T, V> p);
  49. template <class T> void _print(vector <T> v);
  50. template <class T> void _print(vector <vector<T>> v);
  51. template <class T> void _print(set <T> v);
  52. template <class T, class V> void _print(map <T, V> v);
  53. template <class T> void _print(multiset <T> v);
  54. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  55. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  56. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  57. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  58. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  59. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  60.  
  61. /*******************************************************************************************************************************************************************/
  62.  
  63. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  64. int rng(int lim) {
  65.     uniform_int_distribution<int> uid(0,lim-1);
  66.     return uid(rang);
  67. }
  68.  
  69. const int INF = 0x3f3f3f3f;
  70. const int mod = 1e9+7;
  71.  
  72. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  73.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  74.                          
  75. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  76. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  77.  
  78. /******************************************************************************************************************************/
  79.  
  80. class TreeNode {
  81.     public:
  82.         int val;
  83.         TreeNode *left;
  84.         TreeNode *right;
  85.         TreeNode(): val(0), left(NULL), right(NULL) {}
  86.         TreeNode(int data): val(data), left(NULL), right(NULL) {}
  87.         TreeNode(int data, TreeNode *left, TreeNode *right): val(data), left(left), right(right) {}
  88. };
  89.  
  90. void is_bst(TreeNode *root, TreeNode* &prev, bool &ok) {
  91.     // base case
  92.     if(root == NULL) return;
  93.    
  94.     is_bst(root->left, prev, ok);
  95.    
  96.     if(prev != NULL and root->val <= prev->val) {
  97.         ok = 0;
  98.         return;
  99.     }
  100.    
  101.     prev = root;
  102.     is_bst(root->right, prev, ok);
  103. }
  104.  
  105. // We are considering that BSTs can not contain duplicate Nodes.
  106. bool check_bst(TreeNode *root) {
  107.     // initially assuming that the tree is a BST
  108.     bool ok = 1;
  109.    
  110.     TreeNode *prev = NULL;
  111.     is_bst(root, prev, ok);
  112.    
  113.     return ok;
  114. }
  115.  
  116. void solve()
  117. {
  118.     TreeNode* root = new TreeNode(4);
  119.     root->left = new TreeNode(2);
  120.     root->right = new TreeNode(6);
  121.     root->left->left = new TreeNode(1);
  122.     root->left->right = new TreeNode(3);
  123.     root->right->left = new TreeNode(5);
  124.     root->right->right = new TreeNode(7);
  125.    
  126.     if(check_bst(root)) cout << "Yes\n";
  127.     else cout << "No\n";
  128. }
  129.  
  130. int main()
  131. {
  132.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  133.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  134.  
  135.     // #ifndef ONLINE_JUDGE
  136.     //     freopen("input.txt", "r", stdin);
  137.     //     freopen("output.txt", "w", stdout);
  138.     // #endif
  139.    
  140.     // #ifndef ONLINE_JUDGE
  141.     //      freopen("error.txt", "w", stderr);
  142.     // #endif
  143.    
  144.     int t = 1;
  145.     // int test = 1;
  146.     // cin >> t;
  147.     while(t--) {
  148.         // cout << "Case #" << test++ << ": ";
  149.         solve();
  150.     }
  151.  
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement