Algorithm-DS-Problems/check_if_binary_tree_is_bst.cpp at master · ankishb/Algorithm-DS-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

/*This is a function problem.You only need to complete the function given below*/
/* A binary tree node has data, pointer to left child
    and a pointer to right child
struct Node {
    int data;
    Node* left, * right;
}; */
void inorder_trans(Node* root, vector<int> &ans){
    if(root==NULL){
        return;
    }
    inorder_trans(root->left, ans);
    ans.push_back(root->data);
    inorder_trans(root->right, ans);
}

bool isBST(Node* root) {
    vector<int> ans;
    inorder_trans(root, ans);
    for(int i=1; i<ans.size(); i++){
        if(ans[i] < ans[i-1]){
            return false;
        }
    }
    return true;
}


#include<climits>
// left_r == left_range && right_r == right_range
bool isBST(Node* root, int left_r, int right_r){
    if(root == NULL){
      return true;
    }
    // check if root doesn't satisfy BST
    if((root->data <= left_r) || (root->data >= right_r)){
        return false;
    }
    return (isBST(root->left, left_r, root->data) &&
            isBST(root->right, root->data, right_r));
}
bool checkBST(Node* root){
    return isBST(root, INT_MIN, INT_MAX);
}


// easiest, but memory expensive
void inorder(Node* root, vector<int> &ans){
    if(root == NULL){
        return ;
    }
    inorder(root->left, ans);
    ans.push_back(root->data);
    inorder(root->right, ans);
}
bool checkBST(Node* root){
    vector<int> ans;
    inorder(root, ans);
    for(int i=1; i<ans.size(); i++){
        if(ans[i] < ans[i-1]){
            return false;
        }
    }
    return true;
}


// another way, but little bit more better, as it remove previous element from vector
bool inorder_tranversal(Node* root, vector<int> &ans, bool break_flag){
    // if break_flag is set, then return false
    if(break_flag){ return false; }
    if(root == NULL){ return true; }
    bool left_check = inorder_tranversal(root->left, ans, break_flag);
    if(ans.size()>=1){
        if(ans[ans.size()-1] > root->data){
            break_flag = true;
            return false;
        }
    }
    ans.push_back(root->data);
    bool right_check = inorder_tranversal(root->right, ans, break_flag);

    return (left_check && right_check);
}
bool checkBST(Node* root){
    vector<int> ans;
    bool break_flag = false;
    return inorder_tranversal(root, ans, break_flag);
}


  // bool checkBST(Node* root) {
  //  if(root == NULL){
  // return true;
  // }
  // // if both childs are NULL
  // if((root->left == NULL) ||
  // (root->right == NULL)){
  // return true;
  // }
  // // check if right child is present
  // if(root->left == NULL){
  // return (root->data < root->right->data);
  // }
  // // check if left child is present
  // if(root->right == NULL){
  // return (root->data > root->left->data);
  // }
  // // check if both present
  // if((root->data < root->left->data) ||
  // (root->data > root->right->data)){
  // return false;
  // }
  // return (checkBST(root->left) && checkBST(root->right));
  // }