Repository: TheAlgorithms/Java
Pull request #4190 (2023-05-14 10:14:19)

CreateBinaryTreeFromInorderPreorder refactoring
- code refactoring in main class
- removed redundant code
- 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/CreateBinaryTreeFromInorderPreorder.java b/src/main/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorder.java
index d99d167b..99b1fb4e 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorder.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorder.java
@@ -1,6 +1,7 @@
 package com.thealgorithms.datastructures.trees;
 
 import com.thealgorithms.datastructures.trees.BinaryTree.Node;
+
 import java.util.HashMap;
 import java.util.Map;
 
@@ -11,66 +12,37 @@ import java.util.Map;
  * subtree. Based on that index create left and right subtree. Complexity: Time:
  * O(n^2) for each node there is iteration to find index in inorder array Space:
  * Stack size = O(height) = O(lg(n))
- *
+ * <p>
  * Optimized Solution: Instead of iterating over inorder array to find index of
  * root value, create a hashmap and find out the index of root value.
  * Complexity: Time: O(n) hashmap reduced iteration to find index in inorder
  * array Space: O(n) space taken by hashmap
- *
  */
 public class CreateBinaryTreeFromInorderPreorder {
-
-    public static void main(String[] args) {
-        test(new Integer[] {}, new Integer[] {}); // empty tree
-        test(new Integer[] { 1 }, new Integer[] { 1 }); // single node tree
-        test(new Integer[] { 1, 2, 3, 4 }, new Integer[] { 1, 2, 3, 4 }); // right skewed tree
-        test(new Integer[] { 1, 2, 3, 4 }, new Integer[] { 4, 3, 2, 1 }); // left skewed tree
-        test(
-            new Integer[] { 3, 9, 20, 15, 7 },
-            new Integer[] { 9, 3, 15, 20, 7 }
-        ); // normal tree
+    public static Node createTree(final Integer[] preorder, final Integer[] inorder) {
+        if (preorder == null || inorder == null) {
+            return null;
+        }
+        return createTree(preorder, inorder, 0, 0, inorder.length);
     }
 
-    private static void test(
-        final Integer[] preorder,
-        final Integer[] inorder
-    ) {
-        System.out.println(
-            "\n===================================================="
-        );
-        System.out.println("Naive Solution...");
-        BinaryTree root = new BinaryTree(
-            createTree(preorder, inorder, 0, 0, inorder.length)
-        );
-        System.out.println("Preorder Traversal: ");
-        root.preOrder(root.getRoot());
-        System.out.println("\nInorder Traversal: ");
-        root.inOrder(root.getRoot());
-        System.out.println("\nPostOrder Traversal: ");
-        root.postOrder(root.getRoot());
-
-        Map<Integer, Integer> map = new HashMap<>();
+    public static Node createTreeOptimized(final Integer[] preorder, final Integer[] inorder) {
+        if (preorder == null || inorder == null) {
+            return null;
+        }
+        Map<Integer, Integer> inorderMap = new HashMap<>();
         for (int i = 0; i < inorder.length; i++) {
-            map.put(inorder[i], i);
+            inorderMap.put(inorder[i], i);
         }
-        BinaryTree optimizedRoot = new BinaryTree(
-            createTreeOptimized(preorder, inorder, 0, 0, inorder.length, map)
-        );
-        System.out.println("\n\nOptimized solution...");
-        System.out.println("Preorder Traversal: ");
-        optimizedRoot.preOrder(root.getRoot());
-        System.out.println("\nInorder Traversal: ");
-        optimizedRoot.inOrder(root.getRoot());
-        System.out.println("\nPostOrder Traversal: ");
-        optimizedRoot.postOrder(root.getRoot());
+        return createTreeOptimized(preorder, inorderMap, 0, 0, inorder.length);
     }
 
     private static Node createTree(
-        final Integer[] preorder,
-        final Integer[] inorder,
-        final int preStart,
-        final int inStart,
-        final int size
+            final Integer[] preorder,
+            final Integer[] inorder,
+            final int preStart,
+            final int inStart,
+            final int size
     ) {
         if (size == 0) {
             return null;
@@ -78,37 +50,36 @@ public class CreateBinaryTreeFromInorderPreorder {
 
         Node root = new Node(preorder[preStart]);
         int i = inStart;
-        while (preorder[preStart] != inorder[i]) {
+        while (!preorder[preStart].equals(inorder[i])) {
             i++;
         }
         int leftNodesCount = i - inStart;
         int rightNodesCount = size - leftNodesCount - 1;
         root.left =
-            createTree(
-                preorder,
-                inorder,
-                preStart + 1,
-                inStart,
-                leftNodesCount
-            );
+                createTree(
+                        preorder,
+                        inorder,
+                        preStart + 1,
+                        inStart,
+                        leftNodesCount
+                );
         root.right =
-            createTree(
-                preorder,
-                inorder,
-                preStart + leftNodesCount + 1,
-                i + 1,
-                rightNodesCount
-            );
+                createTree(
+                        preorder,
+                        inorder,
+                        preStart + leftNodesCount + 1,
+                        i + 1,
+                        rightNodesCount
+                );
         return root;
     }
 
     private static Node createTreeOptimized(
-        final Integer[] preorder,
-        final Integer[] inorder,
-        final int preStart,
-        final int inStart,
-        final int size,
-        final Map<Integer, Integer> inorderMap
+            final Integer[] preorder,
+            final Map<Integer, Integer> inorderMap,
+            final int preStart,
+            final int inStart,
+            final int size
     ) {
         if (size == 0) {
             return null;
@@ -119,23 +90,21 @@ public class CreateBinaryTreeFromInorderPreorder {
         int leftNodesCount = i - inStart;
         int rightNodesCount = size - leftNodesCount - 1;
         root.left =
-            createTreeOptimized(
-                preorder,
-                inorder,
-                preStart + 1,
-                inStart,
-                leftNodesCount,
-                inorderMap
-            );
+                createTreeOptimized(
+                        preorder,
+                        inorderMap,
+                        preStart + 1,
+                        inStart,
+                        leftNodesCount
+                );
         root.right =
-            createTreeOptimized(
-                preorder,
-                inorder,
-                preStart + leftNodesCount + 1,
-                i + 1,
-                rightNodesCount,
-                inorderMap
-            );
+                createTreeOptimized(
+                        preorder,
+                        inorderMap,
+                        preStart + leftNodesCount + 1,
+                        i + 1,
+                        rightNodesCount
+                );
         return root;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java b/src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java
new file mode 100644
index 00000000..59352f54
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java
@@ -0,0 +1,103 @@
+package com.thealgorithms.datastructures.trees;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+
+/**
+ * @author Albina Gimaletdinova on 14/05/2023
+ */
+public class CreateBinaryTreeFromInorderPreorderTest {
+    @Test
+    public void testOnNullArraysShouldReturnNullTree() {
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(null, null);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(null, null);
+
+        // then
+        Assertions.assertNull(root);
+        Assertions.assertNull(rootOpt);
+    }
+
+    @Test
+    public void testOnEmptyArraysShouldCreateNullTree() {
+        // given
+        Integer[] preorder = {};
+        Integer[] inorder = {};
+
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
+
+        // then
+        Assertions.assertNull(root);
+        Assertions.assertNull(rootOpt);
+    }
+
+    @Test
+    public void testOnSingleNodeTreeShouldCreateCorrectTree() {
+        // given
+        Integer[] preorder = {1};
+        Integer[] inorder = {1};
+
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
+
+        // then
+        checkTree(preorder, inorder, root);
+        checkTree(preorder, inorder, rootOpt);
+    }
+
+    @Test
+    public void testOnRightSkewedTreeShouldCreateCorrectTree() {
+        // given
+        Integer[] preorder = {1, 2, 3, 4};
+        Integer[] inorder = {1, 2, 3, 4};
+
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
+
+        // then
+        checkTree(preorder, inorder, root);
+        checkTree(preorder, inorder, rootOpt);
+    }
+
+    @Test
+    public void testOnLeftSkewedTreeShouldCreateCorrectTree() {
+        // given
+        Integer[] preorder = {1, 2, 3, 4};
+        Integer[] inorder = {4, 3, 2, 1};
+
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
+
+        // then
+        checkTree(preorder, inorder, root);
+        checkTree(preorder, inorder, rootOpt);
+    }
+
+    @Test
+    public void testOnNormalTreeShouldCreateCorrectTree() {
+        // given
+        Integer[] preorder = {3, 9, 20, 15, 7};
+        Integer[] inorder = {9, 3, 15, 20, 7};
+
+        // when
+        BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
+        BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
+
+        // then
+        checkTree(preorder, inorder, root);
+        checkTree(preorder, inorder, rootOpt);
+    }
+
+    private static void checkTree(Integer[] preorder, Integer[] inorder, BinaryTree.Node root) {
+        Assertions.assertNotNull(root);
+        Assertions.assertEquals(PreOrderTraversal.iterativePreOrder(root), Arrays.asList(preorder));
+        Assertions.assertEquals(InorderTraversal.iterativeInorder(root), Arrays.asList(inorder));
+    }
+}