-
Notifications
You must be signed in to change notification settings - Fork 34
/
IsBST-3
82 lines (75 loc) · 2 KB
/
IsBST-3
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
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
template <typename T>
class BinaryTreeNode {
public :
T data;
BinaryTreeNode<T> *left;
BinaryTreeNode<T> *right;
BinaryTreeNode(T data) {
this -> data = data;
left = NULL;
right = NULL;
}
~BinaryTreeNode() {
if(left)
delete left;
if(right)
delete right;
}
};
using namespace std;
BinaryTreeNode<int>* takeInput() {
int rootData;
//cout << "Enter root data : ";
cin >> rootData;
if(rootData == -1) {
return NULL;
}
BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
queue<BinaryTreeNode<int>*> q;
q.push(root);
while(!q.empty()) {
BinaryTreeNode<int> *currentNode = q.front();
q.pop();
int leftChild, rightChild;
//cout << "Enter left child of " << currentNode -> data << " : ";
cin >> leftChild;
if(leftChild != -1) {
BinaryTreeNode<int>* leftNode = new BinaryTreeNode<int>(leftChild);
currentNode -> left =leftNode;
q.push(leftNode);
}
//cout << "Enter right child of " << currentNode -> data << " : ";
cin >> rightChild;
if(rightChild != -1) {
BinaryTreeNode<int>* rightNode = new BinaryTreeNode<int>(rightChild);
currentNode -> right =rightNode;
q.push(rightNode);
}
}
return root;
}
bool isBST3(BinaryTreeNode<int> *root,int min,int max){
if(root==NULL)
return true;
if(root->data>max || root->data<min)
return false;
bool leftOutput = isBST3(root->left,min,root->data-1);
bool rightOutput = isBST3(root->right,root->data+1,max);
return leftOutput && rightOutput;
}
bool isBST(BinaryTreeNode<int> *root){
return isBST3(root,INT_MIN,INT_MAX);
}
int main() {
BinaryTreeNode<int>* root = takeInput();
if(isBST(root)) {
cout << "true" << endl;
}
else {
cout << "false" << endl;
}
delete root;
}