summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2019-06-11 22:21:50 -0500
committerHaidong Ji2019-06-11 22:21:50 -0500
commit578980d5ff80f94c9748d806879b7b707eec441e (patch)
treefd08842ba01121d16aa4267390f5eb865f8d9ce7 /src
parentad183107055509e73c7a0740c1dd633f212d0f51 (diff)
"is it binary search tree" done!
This is not too bad. Since I got the tree traversal done in the last exercise, I just used the in-order traversal as a base and modified a bit.
Diffstat (limited to 'src')
-rw-r--r--src/main/TreeBstCheck.java96
-rw-r--r--src/test/TreeBstCheckTest.java60
2 files changed, 156 insertions, 0 deletions
diff --git a/src/main/TreeBstCheck.java b/src/main/TreeBstCheck.java
new file mode 100644
index 0000000..51f33c4
--- /dev/null
+++ b/src/main/TreeBstCheck.java
@@ -0,0 +1,96 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.*;
+
+public class TreeBstCheck {
+ static class FastScanner {
+ StringTokenizer tok = new StringTokenizer("");
+ BufferedReader in;
+
+ FastScanner() {
+ in = new BufferedReader(new InputStreamReader(System.in));
+ }
+
+ String next() throws IOException {
+ while (!tok.hasMoreElements())
+ tok = new StringTokenizer(in.readLine());
+ return tok.nextToken();
+ }
+
+ int nextInt() throws IOException {
+ return Integer.parseInt(next());
+ }
+ }
+
+ static class TreeOrders {
+ int n;
+ int[] key, left, right;
+
+ void read() throws IOException {
+ FastScanner in = new FastScanner();
+ n = in.nextInt();
+ key = new int[n];
+ left = new int[n];
+ right = new int[n];
+ for (int i = 0; i < n; i++) {
+ key[i] = in.nextInt();
+ left[i] = in.nextInt();
+ right[i] = in.nextInt();
+ }
+ }
+
+ boolean isBst() {
+ if (key.length == 0) return true;
+ Stack<Integer> keyIndexStack = new Stack<>();
+ ArrayList<Integer> result = new ArrayList<>();
+ boolean walkLeft = true;
+ int currentIndex = 0;
+ keyIndexStack.push(currentIndex);
+ while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+ if (walkLeft) {
+ if (left[currentIndex] != -1) {
+ if (key[left[currentIndex]] >= key[currentIndex]) return false;
+ currentIndex = left[currentIndex];
+ keyIndexStack.push(currentIndex);
+ } else {
+ int i = keyIndexStack.pop();
+ if (result.size() > 0) {
+ if (key[i] <= result.get(result.size()-1)) return false;
+ }
+ result.add(key[i]);
+ walkLeft = false;
+ }
+ } else {
+ if (right[currentIndex] != -1) {
+ if (key[right[currentIndex]] <= key[currentIndex]) return false;
+ currentIndex = right[currentIndex];
+ keyIndexStack.push(currentIndex);
+ walkLeft = true;
+ } else {
+ if (!keyIndexStack.empty()) {
+ currentIndex = keyIndexStack.pop();
+ if (result.size() > 0) {
+ if (key[currentIndex] <= result.get(result.size()-1)) return false;
+ }
+ result.add(key[currentIndex]);
+ }
+ }
+ }
+ }
+ return true;
+ }
+
+ }
+
+ static public void main(String[] args) throws IOException {
+ TreeOrders tree = new TreeOrders();
+ tree.read();
+ if (tree.isBst()) {
+ System.out.println("CORRECT");
+ } else
+ System.out.println("INCORRECT");
+
+ }
+
+}
diff --git a/src/test/TreeBstCheckTest.java b/src/test/TreeBstCheckTest.java
new file mode 100644
index 0000000..7002d3e
--- /dev/null
+++ b/src/test/TreeBstCheckTest.java
@@ -0,0 +1,60 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class TreeBstCheckTest {
+ @Test
+ void test() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{2, 1, 3};
+ tt.left = new int[]{1, -1, -1};
+ tt.right = new int[]{2, -1, -1};
+
+ assertTrue(tt.isBst());
+ }
+ @Test
+ void test1() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{1, 2, 3};
+ tt.left = new int[]{1, -1, -1};
+ tt.right = new int[]{2, -1, -1};
+
+ assertFalse(tt.isBst());
+ }
+ @Test
+ void test2() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[0];
+ tt.left = new int[0];
+ tt.right = new int[0];
+
+ assertTrue(tt.isBst());
+ }
+ @Test
+ void test3() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{1, 2, 3, 4, 5};
+ tt.left = new int[]{-1, -1, -1, -1, -1};
+ tt.right = new int[]{1, 2, 3, 4, -1};
+
+ assertTrue(tt.isBst());
+ }
+ @Test
+ void test4() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{4, 2, 6, 1, 3, 5, 7};
+ tt.left = new int[]{1, 3, 5, -1, -1, -1, -1};
+ tt.right = new int[]{2, 4, 6, -1, -1, -1, -1};
+
+ assertTrue(tt.isBst());
+ }
+ @Test
+ void test5() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{4, 2, 1, 5};
+ tt.left = new int[]{1, 2, -1, -1};
+ tt.right = new int[]{-1, 3, -1, -1};
+
+ assertFalse(tt.isBst());
+ }
+}