Reputation: 21
package main;
import java.io.*;
import java.util.*;
public class IsBSTTree {
Set<Integer> set = new HashSet<>();
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String[] line = in.readLine().split(" ");
IsBSTTree solution = new IsBSTTree();
Node root = solution.buildTree(line, 0, line.length - 1);
if (solution.isBstTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) {
out.println("Yes");
} else {
out.println("No");
}
out.flush();
}
Boolean isBstTree(Node node, int min, int max) {
if (node == null)
return true;
if (node.data <= min || node.data >= max)
return false;
if (set.contains(node.data))
return false;
set.add(node.data);
if (isBstTree(node.left, min, node.data) ||
isBstTree(node.right, node.data, max)) {
return false;
}
return false;
}
public Node buildTree(String[] arr, int from, int to) {
if (from > to) return null;
int middle = from + (to - from) / 2;
Node node = new Node();
node.data = Integer.valueOf(arr[middle]);
node.left = buildTree(arr, from, middle - 1);
node.right = buildTree(arr, middle + 1, to);
return node;
}
class Node {
int data;
Node left;
Node right;
}
}
Problem Description
Actual Behavior
The set contains values before the isBstTree method is called.
Questions
Any help or insights would be greatly appreciated!
Upvotes: 0
Views: 22