summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2019-06-12 20:06:47 -0500
committerHaidong Ji2019-06-12 20:06:47 -0500
commit18ae1ea81ee05c62b325bf91813f7d293228df45 (patch)
tree73b478ddbe97463c2b3a8957ddd19a70b0f160fd /src
parent578980d5ff80f94c9748d806879b7b707eec441e (diff)
"is it binary search tree hard" done!
not too bad, just allowing the right node being equal or greater. Two modifications to the code was needed.
Diffstat (limited to 'src')
-rw-r--r--src/main/TreeBstCheck.java4
-rw-r--r--src/test/TreeBstCheckTest.java27
2 files changed, 29 insertions, 2 deletions
diff --git a/src/main/TreeBstCheck.java b/src/main/TreeBstCheck.java
index 51f33c4..4258306 100644
--- a/src/main/TreeBstCheck.java
+++ b/src/main/TreeBstCheck.java
@@ -56,14 +56,14 @@ public class TreeBstCheck {
} else {
int i = keyIndexStack.pop();
if (result.size() > 0) {
- if (key[i] <= result.get(result.size()-1)) return false;
+ 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;
+ if (key[right[currentIndex]] < key[currentIndex]) return false;
currentIndex = right[currentIndex];
keyIndexStack.push(currentIndex);
walkLeft = true;
diff --git a/src/test/TreeBstCheckTest.java b/src/test/TreeBstCheckTest.java
index 7002d3e..35b66b4 100644
--- a/src/test/TreeBstCheckTest.java
+++ b/src/test/TreeBstCheckTest.java
@@ -57,4 +57,31 @@ class TreeBstCheckTest {
assertFalse(tt.isBst());
}
+ @Test
+ void test6() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{2, 1, 2};
+ tt.left = new int[]{1, -1, -1};
+ tt.right = new int[]{2, -1, -1};
+
+ assertTrue(tt.isBst());
+ }
+ @Test
+ void test7() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{2, 2, 3};
+ tt.left = new int[]{1, -1, -1};
+ tt.right = new int[]{2, -1, -1};
+
+ assertFalse(tt.isBst());
+ }
+ @Test
+ void test8() {
+ TreeBstCheck.TreeOrders tt = new TreeBstCheck.TreeOrders();
+ tt.key = new int[]{2147483647};
+ tt.left = new int[]{-1};
+ tt.right = new int[]{-1};
+
+ assertTrue(tt.isBst());
+ }
}