The detailed description of this problem is as follows:
each row contains two values x and y, which denotes that the node with key x is the parent of the node with key y. The first y is the left child of x, the second y is the right child of x. If the y is -1, there is no corresponding child of x . Notice that the keys of all the nodes in the tree are distinct and positive.
Added: I've already found some mistakes in my code: 1. The nodes given in the data set may not be from the first layer to the bottom layer, which means after read one line, I need to search the index of the parent node and then add the child. 2. The isBST() function is not correct since a tree is a binary search tree if the left subtree is recursively smaller than the current node and the right subtree is recursively larger than the current node. The first one is easy to solve but I have no idea how to solve the second one.
Sample Input
4
10 5
10 30
30 20
30 -1
the number on the first row denotes the number of rows below.
for each row, the left number denotes the parent, and the right number denotes the child. If the right number is -1, it means that there is no corresponding child.
Sample Output
YES 2
I think my code can successfully pass the test points when the answer should be "No". However, for those cases that should be "YES + num", my code fails. Could anybody point out the mistakes in my code?
Actually, I am not quite sure about the accurate definition of Binary search tree. For the sample input, I do not think it is a complete binary tree. Do I need to take the number of layers of this tree into consideration?
My idea is quite straightforward, I just read the data and store them into an array and use the property that the left child for a value stored at index i is 2 * i and the right child is 2 * i + 1.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BST {
public static int[] readData() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// get the number of rows
int n = Integer.parseInt(br.readLine());
String[] strs;
int[] res = new int[2 * n];
for (int i = 1; i < n + 1; i++) {
strs = br.readLine().trim().split(" ");
//System.out.println(Arrays.toString(strs));
// read the left and right number of one row resp.
int parent = Integer.parseInt(strs[0]);
int child = Integer.parseInt(strs[1]);
// which means that there is no corresponding child, use 0 to denote null
if (child == -1) {
child = 0;
}
// read the second line with the same parent
if (res[i - 1] == parent) {
// put the child as the right child
res[2 * (i - 1) + 1] = child;
}
else {
res[i] = parent;
res[2 * i] = child;
}
}
br.close();
return res;
}
public static boolean isLeaf(int[] data, int index) {
// if the node is null, it is not a leaf
if (data[index] == 0) return false;
if (2 * index < data.length - 1) {
// the left and right children are both null
if (data[2 * index] == 0 && data[2 * index + 1] == 0) {
return true;
}
// the left and right children are not both null
else {
return false;
}
}
// 2 * index is out of bound
else {
return true;
}
}
public static int countLeaf(int[] data) {
int count = 0;
for (int i = 1; i < data.length; i++) {
// if the node is a leaf, count it
if (isLeaf(data, i)) count++;
}
return count;
}
public static boolean checkBSTprop(int[] data, int index) {
// no child can be found
if (2 * index >= data.length) {
return true;
}
// no child
if (data[2 * index] == 0 && data[2 * index + 1] == 0) {
return true;
}
// left child is 0, right child is nonzero
if (data[2 * index] == 0 && data[2 * index + 1] > data[index]) {
return true;
}
// right child is 0, left child is nonzero
if (data[2 * index + 1] == 0 && data[2 * index] < data[index]) {
return true;
}
// both children are nonzero
if (data[2 * index] < data[index] && data[2 * index + 1] > data[index]) {
return true;
}
// none of the conditions are satisfied
return false;
}
public static boolean isBST(int[] data) {
for (int i = 1; i < data.length; i++) {
if (!checkBSTprop(data, i)) {
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
int[] res = readData();
int num = countLeaf(res);
/*
System.out.println(Arrays.toString(res));
System.out.println(countLeaf(res));
System.out.println(checkBSTprop(res, 1));
System.out.println(checkBSTprop(res, 2));
System.out.println(checkBSTprop(res, 3));
System.out.println(checkBSTprop(res, 6));
System.out.println(isBST(res));
*/
if (isBST(res)) {
System.out.println("YES " + num);
}
else {
System.out.println("NO");
}
}
}
Your approach will not work consistently, because:
For this reason you cannot use i to define where in the array to store a node's value, with a formula like 2 * (i - 1) + 1, nor can you check that the parent already has appeared before with res[i - 1].
For instance, your program will answer "NO" for this valid BST:
6
3 2
3 -1
2 1
2 -1
1 -1
1 -1
And if we input the same tree, without the unnecessary 1 -1 (twice), like this:
4
3 2
3 -1
2 1
2 -1
...then there is an out-of-bounds exception.
Secondly, it is not enough in isBST to compare the value of a child with its parent. Even when that comparison is fine, you could still have an invalid BST, like for example this one:
4
/
1
\
10
This is invalid, as the only valid (distinct) integer values for that leaf are 2 or 3. So you need to have to check against a range that sifts down the recursion tree.
A pragmatic solution is to really build the tree with Node class instances, and let isBST be an instance method of that class, which takes into account also this range requirement.