Repository: TheAlgorithms/Java
Pull request #4222 (2023-06-26 10:58:39)

BinaryTreeIsBalanced algorithm refactoring
Changes:
- code refactoring in main algorithm class
- removed redundant code
- added unit tests
- fixed spelling in the comments

<!-- 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/DIRECTORY.md b/DIRECTORY.md
index d19c59d9..4e20adc8 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -586,6 +586,7 @@
               * [BSTRecursiveTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/BSTRecursiveTest.java)
               * [CeilInBinarySearchTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CeilInBinarySearchTreeTest.java)
               * [CheckBinaryTreeIsValidBSTTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBSTTest.java)
+              * [CheckIfBinaryTreeBalancedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java)
               * [CheckTreeIsSymmetricTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetricTest.java)
               * [CreateBinaryTreeFromInorderPreorderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java)
               * [InorderTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/InorderTraversalTest.java)
@@ -687,6 +688,7 @@
             * [CountWordsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CountWordsTest.java)
             * [CRC16Test](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CRC16Test.java)
             * [CRCAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CRCAlgorithmTest.java)
+            * [EulersFunctionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/EulersFunctionTest.java)
             * [FirstFitCPUTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/FirstFitCPUTest.java)
             * [KadaneAlogrithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java)
             * [LineSweepTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LineSweepTest.java)
@@ -695,6 +697,7 @@
             * [NewManShanksPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NewManShanksPrimeTest.java)
             * [NextFitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NextFitTest.java)
             * [PasswordGenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/PasswordGenTest.java)
+            * [SieveOfEratosthenesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/SieveOfEratosthenesTest.java)
             * [TestPrintMatrixInSpiralOrder](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/TestPrintMatrixInSpiralOrder.java)
             * [TwoPointersTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/TwoPointersTest.java)
             * [UniquePathsTests](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/UniquePathsTests.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalanced.java b/src/main/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalanced.java
index c4d6ff94..9dd50245 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalanced.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalanced.java
@@ -5,9 +5,9 @@ import java.util.Stack;
 
 /**
  * This class will check if a BinaryTree is balanced. A balanced binary tree is
- * defined as a binary tree where the differenced in height between the left and
+ * defined as a binary tree where the difference in height between the left and
  * right subtree of each node differs by at most one.
- *
+ * <p>
  * This can be done in both an iterative and recursive fashion. Below,
  * `isBalancedRecursive()` is implemented in a recursive fashion, and
  * `isBalancedIterative()` is implemented in an iterative fashion.
@@ -15,59 +15,22 @@ import java.util.Stack;
  * @author [Ian Cowan](https://github.com/iccowan)
  */
 public class CheckIfBinaryTreeBalanced {
-
-    /**
-     * This class implements the BinaryTree for these algorithms
-     */
-    class BinaryTree {
-
-        /**
-         * The root node of the binary tree
-         */
-        BTNode root = null;
-    }
-
-    /**
-     * This class implements the nodes for the binary tree
-     */
-    class BTNode {
-
-        /**
-         * The value of the node
-         */
-        int value;
-
-        /**
-         * The left child of the node
-         */
-        BTNode left = null;
-
-        /**
-         * The right child of the node
-         */
-        BTNode right = null;
-
-        /**
-         * Constructor
-         */
-        BTNode(int value) {
-            this.value = value;
-        }
-    }
-
     /**
      * Recursive is BT balanced implementation
      *
-     * @param binaryTree The binary tree to check if balanced
+     * @param root The binary tree to check if balanced
      */
-    public boolean isBalancedRecursive(BinaryTree binaryTree) {
+    public static boolean isBalancedRecursive(BinaryTree.Node root) {
+        if (root == null) {
+            return true;
+        }
         // Create an array of length 1 to keep track of our balance
-        // Default to true. We use an array so we have an efficient mutable object
+        // Default to true. We use an array, so we have an efficient mutable object
         boolean[] isBalanced = new boolean[1];
         isBalanced[0] = true;
 
-        // Check for balance and return whether or not we are balanced
-        isBalancedRecursive(binaryTree.root, 0, isBalanced);
+        // Check for balance and return whether we are balanced
+        isBalancedRecursive(root, 0, isBalanced);
         return isBalanced[0];
     }
 
@@ -76,11 +39,11 @@ public class CheckIfBinaryTreeBalanced {
      * recursion. We effectively perform a modified post-order traversal where
      * we are looking at the heights of both children of each node in the tree
      *
-     * @param node The current node to explore
-     * @param depth The current depth of the node
+     * @param node       The current node to explore
+     * @param depth      The current depth of the node
      * @param isBalanced The array of length 1 keeping track of our balance
      */
-    private int isBalancedRecursive(BTNode node, int depth, boolean[] isBalanced) {
+    private static int isBalancedRecursive(BinaryTree.Node node, int depth, boolean[] isBalanced) {
         // If the node is null, we should not explore it and the height is 0
         // If the tree is already not balanced, might as well stop because we
         // can't make it balanced now!
@@ -106,22 +69,26 @@ public class CheckIfBinaryTreeBalanced {
     /**
      * Iterative is BT balanced implementation
      */
-    public boolean isBalancedIterative(BinaryTree binaryTree) {
+    public static boolean isBalancedIterative(BinaryTree.Node root) {
+        if (root == null) {
+            return true;
+        }
+
         // Default that we are balanced and our algo will prove it wrong
         boolean isBalanced = true;
 
         // Create a stack for our post order traversal
-        Stack<BTNode> nodeStack = new Stack<BTNode>();
+        Stack<BinaryTree.Node> nodeStack = new Stack<>();
 
         // For post order traversal, we'll have to keep track of where we
         // visited last
-        BTNode lastVisited = null;
+        BinaryTree.Node lastVisited = null;
 
         // Create a HashMap to keep track of the subtree heights for each node
-        HashMap<BTNode, Integer> subtreeHeights = new HashMap<BTNode, Integer>();
+        HashMap<BinaryTree.Node, Integer> subtreeHeights = new HashMap<>();
 
         // We begin at the root of the tree
-        BTNode node = binaryTree.root;
+        BinaryTree.Node node = root;
 
         // We loop while:
         // - the node stack is empty and the node we explore is null
@@ -165,7 +132,7 @@ public class CheckIfBinaryTreeBalanced {
                     }
 
                     // The height of the subtree containing this node is the
-                    // max of the left and right subtree heighs plus 1
+                    // max of the left and right subtree heights plus 1
                     subtreeHeights.put(node, Math.max(rightHeight, leftHeight) + 1);
 
                     // We've now visited this node, so we pop it from the stack
@@ -182,86 +149,7 @@ public class CheckIfBinaryTreeBalanced {
             }
         }
 
-        // Return whether or not the tree is balanced
+        // Return whether the tree is balanced
         return isBalanced;
     }
-
-    /**
-     * Generates the following unbalanced binary tree for testing 0 / \ / \ 0 0
-     * / / \ / / \ 0 0 0 / \ / \ 0 0 / / 0
-     */
-    private BinaryTree buildUnbalancedTree() {
-        BinaryTree tree = new BinaryTree();
-        tree.root = new BTNode(0);
-
-        BTNode root = tree.root;
-        root.left = new BTNode(0);
-        root.right = new BTNode(0);
-
-        BTNode left = root.left;
-        BTNode right = root.right;
-
-        left.left = new BTNode(0);
-        right.left = new BTNode(0);
-        right.right = new BTNode(0);
-        right.left.right = new BTNode(0);
-
-        left = left.left;
-        left.left = new BTNode(0);
-        left.left.left = new BTNode(0);
-        left.left.left.left = new BTNode(0);
-
-        return tree;
-    }
-
-    /**
-     * Generates the following balanced binary tree for testing 0 / \ / \ 0 0 /
-     * \ / \ / 0 / \ 0 0 0 / / / / 0 0
-     */
-    private BinaryTree buildBalancedTree() {
-        BinaryTree tree = new BinaryTree();
-        tree.root = new BTNode(0);
-
-        BTNode root = tree.root;
-        root.left = new BTNode(0);
-        root.right = new BTNode(0);
-
-        BTNode left = root.left;
-        BTNode right = root.right;
-
-        left.left = new BTNode(0);
-        left.right = new BTNode(0);
-        right.left = new BTNode(0);
-        right.right = new BTNode(0);
-
-        right.right.left = new BTNode(0);
-
-        left.left.left = new BTNode(0);
-
-        return tree;
-    }
-
-    /**
-     * Main
-     */
-    public static void main(String[] args) {
-        // We create a new object to check the binary trees for balance
-        CheckIfBinaryTreeBalanced balanceCheck = new CheckIfBinaryTreeBalanced();
-
-        // Build a balanced and unbalanced binary tree
-        BinaryTree balancedTree = balanceCheck.buildBalancedTree();
-        BinaryTree unbalancedTree = balanceCheck.buildUnbalancedTree();
-
-        // Run basic tests on the algorithms to check for balance
-        boolean isBalancedRB = balanceCheck.isBalancedRecursive(balancedTree); // true
-        boolean isBalancedRU = balanceCheck.isBalancedRecursive(unbalancedTree); // false
-        boolean isBalancedIB = balanceCheck.isBalancedIterative(balancedTree); // true
-        boolean isBalancedIU = balanceCheck.isBalancedIterative(unbalancedTree); // false
-
-        // Print the results
-        System.out.println("isBalancedRB: " + isBalancedRB);
-        System.out.println("isBalancedRU: " + isBalancedRU);
-        System.out.println("isBalancedIB: " + isBalancedIB);
-        System.out.println("isBalancedIU: " + isBalancedIU);
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java b/src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java
new file mode 100644
index 00000000..0eb234d6
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java
@@ -0,0 +1,84 @@
+package com.thealgorithms.datastructures.trees;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test check both implemented ways, iterative and recursive algorithms.
+ *
+ * @author Albina Gimaletdinova on 26/06/2023
+ */
+public class CheckIfBinaryTreeBalancedTest {
+    @Test
+    public void testRootNull() {
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(null));
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(null));
+    }
+
+    @Test
+    public void testOneNode() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {Integer.MIN_VALUE});
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
+    }
+
+    /*
+     9    <-- Math.abs(height(left) - height(right)) == 0
+    / \
+   7   13
+  /\   / \
+ 3  8 10 20
+*/
+    @Test
+    public void testBinaryTreeIsBalancedEqualSubtreeHeights() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8, 10, 20});
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
+    }
+
+    /*
+     9    <-- Math.abs(height(left) - height(right)) == 1
+    / \
+   7   13
+  /\
+ 3  8
+*/
+    @Test
+    public void testBinaryTreeIsBalancedWithDifferentHeights() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8});
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
+        assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
+    }
+
+    /*
+         9  <-- only left tree exists, Math.abs(height(left) - height(right)) > 1
+        /
+       7
+      /\
+     3  8
+    */
+    @Test
+    public void testBinaryTreeNotBalanced() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, null, 3, 8});
+        assertFalse(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
+        assertFalse(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
+    }
+
+    /*
+         9    <-- Math.abs(height(left) - height(right)) > 1
+        / \
+       7   13
+      /\
+     3  8
+    /
+   11
+*/
+    @Test
+    public void testBinaryTreeNotBalancedBecauseLeftTreeNotBalanced() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8, null, null, 11});
+        assertFalse(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
+        assertFalse(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
+    }
+}