-
Notifications
You must be signed in to change notification settings - Fork 0
/
Check_for_BST.java
151 lines (129 loc) · 3.77 KB
/
Check_for_BST.java
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*Question:Check for BST
Link: https://practice.geeksforgeeks.org/problems/check-for-bst/1
Input:
2
/ \
1 3
Output: 1
Explanation:
The left subtree of root node contains node
with key lesser than the root nodes key and
the right subtree of root node contains node
with key greater than the root nodes key.
Hence, the tree is a BST.
Input:
2
\
7
\
6
\
5
\
9
\
2
\
6
Output: 0
Explanation:
Since the node with value 7 has right subtree
nodes with keys less than 7, this is not a BST.
*/
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left=null;
right=null;
}
}
public class Check_for_BST {
static Node buildTree(String str){
if(str.length()==0 || str.charAt(0)=='N'){
return null;
}
String ip[] = str.split(" ");
// Create the root of the tree
Node root = new Node(Integer.parseInt(ip[0]));
// Push the root to the queue
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// Starting from the second element
int i = 1;
while(queue.size()>0 && i < ip.length) {
// Get and remove the front of the queue
Node currNode = queue.peek();
queue.remove();
// Get the current node's value from the string
String currVal = ip[i];
// If the left child is not null
if(!currVal.equals("N")) {
// Create the left child for the current node
currNode.left = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.left);
}
// For the right child
i++;
if(i >= ip.length)
break;
currVal = ip[i];
// If the right child is not null
if(!currVal.equals("N")) {
// Create the right child for the current node
currNode.right = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.right);
}
i++;
}
return root;
}
static void printInorder(Node root)
{
if(root == null)
return;
printInorder(root.left);
System.out.print(root.data+" ");
printInorder(root.right);
}
public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t > 0){
String s = br.readLine();
Node root = buildTree(s);
Solution g = new Solution();
if(g.isBST(root))
System.out.println(1);
else
System.out.println(0);
t--;
}
}
}
class Solution
{
//Function to check whether a Binary Tree is BST or not.
boolean isbst(Node root,int min,int max){
if(root==null){
return true;
}
if(root.data<=min || root.data>=max)
return false;
return isbst(root.left,min,root.data) && isbst(root.right,root.data,max);
}
boolean isBST(Node root)
{
// code here.
// int mi=I
return isbst(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
}