Repository: TheAlgorithms/Java
Pull request #4162 (2023-04-20 12:38:45)

BSTFromSortedArray refactoring, added unit tests
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/BSTFromSortedArray.java b/src/main/java/com/thealgorithms/datastructures/trees/BSTFromSortedArray.java
new file mode 100644
index 00000000..9066a6f2
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/trees/BSTFromSortedArray.java
@@ -0,0 +1,33 @@
+package com.thealgorithms.datastructures.trees;
+
+import com.thealgorithms.datastructures.trees.BinaryTree.Node;
+
+/**
+ * Given a sorted array. Create a balanced binary search tree from it.
+ *
+ * Steps: 1. Find the middle element of array. This will act as root 2. Use the
+ * left half recursively to create left subtree 3. Use the right half
+ * recursively to create right subtree
+ */
+public class BSTFromSortedArray {
+    public static Node createBST(int[] array) {
+        if (array == null || array.length == 0) {
+            return null;
+        }
+        return createBST(array, 0, array.length - 1);
+    }
+
+    private static Node createBST(int[] array, int startIdx, int endIdx) {
+        // No element left.
+        if (startIdx > endIdx) {
+            return null;
+        }
+        int mid = startIdx + (endIdx - startIdx) / 2;
+
+        // middle element will be the root
+        Node root = new Node(array[mid]);
+        root.left = createBST(array, startIdx, mid - 1);
+        root.right = createBST(array, mid + 1, endIdx);
+        return root;
+    }
+}
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/ValidBSTOrNot.java b/src/main/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBST.java
similarity index 96%
rename from src/main/java/com/thealgorithms/datastructures/trees/ValidBSTOrNot.java
rename to src/main/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBST.java
index 65c4e107..13246944 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/ValidBSTOrNot.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBST.java
@@ -8,7 +8,7 @@ package com.thealgorithms.datastructures.trees;
  *    where 'min' and 'max' values represent the child nodes (left, right).
  * 2. The smallest possible node value is Integer.MIN_VALUE, the biggest - Integer.MAX_VALUE.
  */
-public class ValidBSTOrNot {
+public class CheckBinaryTreeIsValidBST {
     public static boolean isBST(BinaryTree.Node root) {
         return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
     }
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/CreateBSTFromSortedArray.java b/src/main/java/com/thealgorithms/datastructures/trees/CreateBSTFromSortedArray.java
deleted file mode 100644
index e43b8c28..00000000
--- a/src/main/java/com/thealgorithms/datastructures/trees/CreateBSTFromSortedArray.java
+++ /dev/null
@@ -1,44 +0,0 @@
-package com.thealgorithms.datastructures.trees;
-
-import com.thealgorithms.datastructures.trees.BinaryTree.Node;
-
-/**
- * Given a sorted array. Create a balanced binary search tree from it.
- *
- * Steps: 1. Find the middle element of array. This will act as root 2. Use the
- * left half recursively to create left subtree 3. Use the right half
- * recursively to create right subtree
- */
-public class CreateBSTFromSortedArray {
-
-    public static void main(String[] args) {
-        test(new int[] {});
-        test(new int[] { 1, 2, 3 });
-        test(new int[] { 1, 2, 3, 4, 5 });
-        test(new int[] { 1, 2, 3, 4, 5, 6, 7 });
-    }
-
-    private static void test(int[] array) {
-        BinaryTree root = new BinaryTree(createBst(array, 0, array.length - 1));
-        System.out.println("\n\nPreorder Traversal: ");
-        root.preOrder(root.getRoot());
-        System.out.println("\nInorder Traversal: ");
-        root.inOrder(root.getRoot());
-        System.out.println("\nPostOrder Traversal: ");
-        root.postOrder(root.getRoot());
-    }
-
-    private static Node createBst(int[] array, int start, int end) {
-        // No element left.
-        if (start > end) {
-            return null;
-        }
-        int mid = start + (end - start) / 2;
-
-        // middle element will be the root
-        Node root = new Node(array[mid]);
-        root.left = createBst(array, start, mid - 1);
-        root.right = createBst(array, mid + 1, end);
-        return root;
-    }
-}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/BSTFromSortedArrayTest.java b/src/test/java/com/thealgorithms/datastructures/trees/BSTFromSortedArrayTest.java
new file mode 100644
index 00000000..83458f6f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/BSTFromSortedArrayTest.java
@@ -0,0 +1,47 @@
+package com.thealgorithms.datastructures.trees;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+/**
+ * @author Albina Gimaletdinova on 20/04/2023
+ */
+public class BSTFromSortedArrayTest {
+    @Test
+    public void testNullArray() {
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(null);
+        Assertions.assertNull(actualBST);
+    }
+
+    @Test
+    public void testEmptyArray() {
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(new int[]{});
+        Assertions.assertNull(actualBST);
+    }
+
+    @Test
+    public void testSingleElementArray() {
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(new int[]{Integer.MIN_VALUE});
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(actualBST));
+    }
+
+    @Test
+    public void testCreateBSTFromSmallArray() {
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(new int[]{1, 2, 3});
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(actualBST));
+    }
+
+    @Test
+    public void testCreateBSTFromLongerArray() {
+        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(array);
+        Assertions.assertTrue(CheckBinaryTreeIsValidBST.isBST(actualBST));
+    }
+
+    @Test
+    public void testShouldNotCreateBSTFromNonSortedArray() {
+        int[] array = {10, 2, 3, 4, 5, 6, 7, 8, 9, 1};
+        BinaryTree.Node actualBST = BSTFromSortedArray.createBST(array);
+        Assertions.assertFalse(CheckBinaryTreeIsValidBST.isBST(actualBST));
+    }
+}
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/ValidBSTOrNotTest.java b/src/test/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBSTTest.java
similarity index 79%
rename from src/test/java/com/thealgorithms/datastructures/trees/ValidBSTOrNotTest.java
rename to src/test/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBSTTest.java
index b3189a80..041b2eea 100644
--- a/src/test/java/com/thealgorithms/datastructures/trees/ValidBSTOrNotTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBSTTest.java
@@ -8,16 +8,16 @@ import static org.junit.jupiter.api.Assertions.assertTrue;
 /**
  * @author Albina Gimaletdinova on 17/02/2023
  */
-public class ValidBSTOrNotTest {
+public class CheckBinaryTreeIsValidBSTTest {
     @Test
     public void testRootNull() {
-        assertTrue(ValidBSTOrNot.isBST(null));
+        assertTrue(CheckBinaryTreeIsValidBST.isBST(null));
     }
 
     @Test
     public void testOneNode() {
         final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{Integer.MIN_VALUE});
-        assertTrue(ValidBSTOrNot.isBST(root));
+        assertTrue(CheckBinaryTreeIsValidBST.isBST(root));
     }
 
     /*
@@ -30,7 +30,7 @@ public class ValidBSTOrNotTest {
     @Test
     public void testBinaryTreeIsBST() {
         final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{9, 7, 13, 3, 8, 10, 20});
-        assertTrue(ValidBSTOrNot.isBST(root));
+        assertTrue(CheckBinaryTreeIsValidBST.isBST(root));
     }
 
     /*
@@ -43,7 +43,7 @@ public class ValidBSTOrNotTest {
     @Test
     public void testBinaryTreeWithDuplicatedNodesIsNotBST() {
         final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{9, 7, 13, 3, 8, 10, 13});
-        assertFalse(ValidBSTOrNot.isBST(root));
+        assertFalse(CheckBinaryTreeIsValidBST.isBST(root));
     }
 
     /*
@@ -56,6 +56,6 @@ public class ValidBSTOrNotTest {
     @Test
     public void testBinaryTreeIsNotBST() {
         final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{9, 7, 13, 3, 8, 10, 12});
-        assertFalse(ValidBSTOrNot.isBST(root));
+        assertFalse(CheckBinaryTreeIsValidBST.isBST(root));
     }
 }