From 578980d5ff80f94c9748d806879b7b707eec441e Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 11 Jun 2019 22:21:50 -0500
Subject: "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.
---
 src/main/TreeBstCheck.java     | 96 ++++++++++++++++++++++++++++++++++++++++++
 src/test/TreeBstCheckTest.java | 60 ++++++++++++++++++++++++++
 2 files changed, 156 insertions(+)
 create mode 100644 src/main/TreeBstCheck.java
 create mode 100644 src/test/TreeBstCheckTest.java

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());
+    }
+}
-- 
cgit v1.2.3