Skip to content

Commit bc699b8

Browse files
albina-astralbina-astr
authored
Refactor BinaryTreeIsBalanced algorithm (TheAlgorithms#4222)
1 parent 05ca93e commit bc699b8

File tree

3 files changed

+111
-136
lines changed

3 files changed

+111
-136
lines changed

‎DIRECTORY.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -586,6 +586,7 @@
586586
* [BSTRecursiveTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/BSTRecursiveTest.java)
587587
* [CeilInBinarySearchTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CeilInBinarySearchTreeTest.java)
588588
* [CheckBinaryTreeIsValidBSTTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckBinaryTreeIsValidBSTTest.java)
589+
* [CheckIfBinaryTreeBalancedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java)
589590
* [CheckTreeIsSymmetricTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetricTest.java)
590591
* [CreateBinaryTreeFromInorderPreorderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java)
591592
* [InorderTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/InorderTraversalTest.java)
@@ -687,6 +688,7 @@
687688
* [CountWordsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CountWordsTest.java)
688689
* [CRC16Test](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CRC16Test.java)
689690
* [CRCAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CRCAlgorithmTest.java)
691+
* [EulersFunctionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/EulersFunctionTest.java)
690692
* [FirstFitCPUTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/FirstFitCPUTest.java)
691693
* [KadaneAlogrithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java)
692694
* [LineSweepTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LineSweepTest.java)
@@ -695,6 +697,7 @@
695697
* [NewManShanksPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NewManShanksPrimeTest.java)
696698
* [NextFitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/NextFitTest.java)
697699
* [PasswordGenTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/PasswordGenTest.java)
700+
* [SieveOfEratosthenesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/SieveOfEratosthenesTest.java)
698701
* [TestPrintMatrixInSpiralOrder](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/TestPrintMatrixInSpiralOrder.java)
699702
* [TwoPointersTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/TwoPointersTest.java)
700703
* [UniquePathsTests](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/UniquePathsTests.java)

‎src/main/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalanced.java‎

Lines changed: 24 additions & 136 deletions
Original file line numberDiff line numberDiff line change
@@ -5,69 +5,32 @@
55

66
/**
77
* This class will check if a BinaryTree is balanced. A balanced binary tree is
8-
* defined as a binary tree where the differenced in height between the left and
8+
* defined as a binary tree where the difference in height between the left and
99
* right subtree of each node differs by at most one.
10-
*
10+
* <p>
1111
* This can be done in both an iterative and recursive fashion. Below,
1212
* `isBalancedRecursive()` is implemented in a recursive fashion, and
1313
* `isBalancedIterative()` is implemented in an iterative fashion.
1414
*
1515
* @author [Ian Cowan](https://github.com/iccowan)
1616
*/
1717
public class CheckIfBinaryTreeBalanced {
18-
19-
/**
20-
* This class implements the BinaryTree for these algorithms
21-
*/
22-
class BinaryTree {
23-
24-
/**
25-
* The root node of the binary tree
26-
*/
27-
BTNode root = null;
28-
}
29-
30-
/**
31-
* This class implements the nodes for the binary tree
32-
*/
33-
class BTNode {
34-
35-
/**
36-
* The value of the node
37-
*/
38-
int value;
39-
40-
/**
41-
* The left child of the node
42-
*/
43-
BTNode left = null;
44-
45-
/**
46-
* The right child of the node
47-
*/
48-
BTNode right = null;
49-
50-
/**
51-
* Constructor
52-
*/
53-
BTNode(int value) {
54-
this.value = value;
55-
}
56-
}
57-
5818
/**
5919
* Recursive is BT balanced implementation
6020
*
61-
* @param binaryTree The binary tree to check if balanced
21+
* @param root The binary tree to check if balanced
6222
*/
63-
public boolean isBalancedRecursive(BinaryTree binaryTree) {
23+
public static boolean isBalancedRecursive(BinaryTree.Node root) {
24+
if (root == null) {
25+
return true;
26+
}
6427
// Create an array of length 1 to keep track of our balance
65-
// Default to true. We use an array so we have an efficient mutable object
28+
// Default to true. We use an array, so we have an efficient mutable object
6629
boolean[] isBalanced = new boolean[1];
6730
isBalanced[0] = true;
6831

69-
// Check for balance and return whether or not we are balanced
70-
isBalancedRecursive(binaryTree.root, 0, isBalanced);
32+
// Check for balance and return whether we are balanced
33+
isBalancedRecursive(root, 0, isBalanced);
7134
return isBalanced[0];
7235
}
7336

@@ -76,11 +39,11 @@ public boolean isBalancedRecursive(BinaryTree binaryTree) {
7639
* recursion. We effectively perform a modified post-order traversal where
7740
* we are looking at the heights of both children of each node in the tree
7841
*
79-
* @param node The current node to explore
80-
* @param depth The current depth of the node
42+
* @param node The current node to explore
43+
* @param depth The current depth of the node
8144
* @param isBalanced The array of length 1 keeping track of our balance
8245
*/
83-
private int isBalancedRecursive(BTNode node, int depth, boolean[] isBalanced) {
46+
private static int isBalancedRecursive(BinaryTree.Node node, int depth, boolean[] isBalanced) {
8447
// If the node is null, we should not explore it and the height is 0
8548
// If the tree is already not balanced, might as well stop because we
8649
// can't make it balanced now!
@@ -106,22 +69,26 @@ private int isBalancedRecursive(BTNode node, int depth, boolean[] isBalanced) {
10669
/**
10770
* Iterative is BT balanced implementation
10871
*/
109-
public boolean isBalancedIterative(BinaryTree binaryTree) {
72+
public static boolean isBalancedIterative(BinaryTree.Node root) {
73+
if (root == null) {
74+
return true;
75+
}
76+
11077
// Default that we are balanced and our algo will prove it wrong
11178
boolean isBalanced = true;
11279

11380
// Create a stack for our post order traversal
114-
Stack<BTNode> nodeStack = new Stack<BTNode>();
81+
Stack<BinaryTree.Node> nodeStack = new Stack<>();
11582

11683
// For post order traversal, we'll have to keep track of where we
11784
// visited last
118-
BTNode lastVisited = null;
85+
BinaryTree.Node lastVisited = null;
11986

12087
// Create a HashMap to keep track of the subtree heights for each node
121-
HashMap<BTNode, Integer> subtreeHeights = new HashMap<BTNode, Integer>();
88+
HashMap<BinaryTree.Node, Integer> subtreeHeights = new HashMap<>();
12289

12390
// We begin at the root of the tree
124-
BTNode node = binaryTree.root;
91+
BinaryTree.Node node = root;
12592

12693
// We loop while:
12794
// - the node stack is empty and the node we explore is null
@@ -165,7 +132,7 @@ public boolean isBalancedIterative(BinaryTree binaryTree) {
165132
}
166133

167134
// The height of the subtree containing this node is the
168-
// max of the left and right subtree heighs plus 1
135+
// max of the left and right subtree heights plus 1
169136
subtreeHeights.put(node, Math.max(rightHeight, leftHeight) + 1);
170137

171138
// We've now visited this node, so we pop it from the stack
@@ -182,86 +149,7 @@ public boolean isBalancedIterative(BinaryTree binaryTree) {
182149
}
183150
}
184151

185-
// Return whether or not the tree is balanced
152+
// Return whether the tree is balanced
186153
return isBalanced;
187154
}
188-
189-
/**
190-
* Generates the following unbalanced binary tree for testing 0 / \ / \ 0 0
191-
* / / \ / / \ 0 0 0 / \ / \ 0 0 / / 0
192-
*/
193-
private BinaryTree buildUnbalancedTree() {
194-
BinaryTree tree = new BinaryTree();
195-
tree.root = new BTNode(0);
196-
197-
BTNode root = tree.root;
198-
root.left = new BTNode(0);
199-
root.right = new BTNode(0);
200-
201-
BTNode left = root.left;
202-
BTNode right = root.right;
203-
204-
left.left = new BTNode(0);
205-
right.left = new BTNode(0);
206-
right.right = new BTNode(0);
207-
right.left.right = new BTNode(0);
208-
209-
left = left.left;
210-
left.left = new BTNode(0);
211-
left.left.left = new BTNode(0);
212-
left.left.left.left = new BTNode(0);
213-
214-
return tree;
215-
}
216-
217-
/**
218-
* Generates the following balanced binary tree for testing 0 / \ / \ 0 0 /
219-
* \ / \ / 0 / \ 0 0 0 / / / / 0 0
220-
*/
221-
private BinaryTree buildBalancedTree() {
222-
BinaryTree tree = new BinaryTree();
223-
tree.root = new BTNode(0);
224-
225-
BTNode root = tree.root;
226-
root.left = new BTNode(0);
227-
root.right = new BTNode(0);
228-
229-
BTNode left = root.left;
230-
BTNode right = root.right;
231-
232-
left.left = new BTNode(0);
233-
left.right = new BTNode(0);
234-
right.left = new BTNode(0);
235-
right.right = new BTNode(0);
236-
237-
right.right.left = new BTNode(0);
238-
239-
left.left.left = new BTNode(0);
240-
241-
return tree;
242-
}
243-
244-
/**
245-
* Main
246-
*/
247-
public static void main(String[] args) {
248-
// We create a new object to check the binary trees for balance
249-
CheckIfBinaryTreeBalanced balanceCheck = new CheckIfBinaryTreeBalanced();
250-
251-
// Build a balanced and unbalanced binary tree
252-
BinaryTree balancedTree = balanceCheck.buildBalancedTree();
253-
BinaryTree unbalancedTree = balanceCheck.buildUnbalancedTree();
254-
255-
// Run basic tests on the algorithms to check for balance
256-
boolean isBalancedRB = balanceCheck.isBalancedRecursive(balancedTree); // true
257-
boolean isBalancedRU = balanceCheck.isBalancedRecursive(unbalancedTree); // false
258-
boolean isBalancedIB = balanceCheck.isBalancedIterative(balancedTree); // true
259-
boolean isBalancedIU = balanceCheck.isBalancedIterative(unbalancedTree); // false
260-
261-
// Print the results
262-
System.out.println("isBalancedRB: " + isBalancedRB);
263-
System.out.println("isBalancedRU: " + isBalancedRU);
264-
System.out.println("isBalancedIB: " + isBalancedIB);
265-
System.out.println("isBalancedIU: " + isBalancedIU);
266-
}
267155
}

‎src/test/java/com/thealgorithms/datastructures/trees/CheckIfBinaryTreeBalancedTest.java‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.thealgorithms.datastructures.trees;
2+
3+
import static org.junit.jupiter.api.Assertions.assertFalse;
4+
import static org.junit.jupiter.api.Assertions.assertTrue;
5+
6+
import org.junit.jupiter.api.Test;
7+
8+
/**
9+
* Test check both implemented ways, iterative and recursive algorithms.
10+
*
11+
* @author Albina Gimaletdinova on 26/06/2023
12+
*/
13+
public class CheckIfBinaryTreeBalancedTest {
14+
@Test
15+
public void testRootNull() {
16+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(null));
17+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(null));
18+
}
19+
20+
@Test
21+
public void testOneNode() {
22+
final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {Integer.MIN_VALUE});
23+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
24+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
25+
}
26+
27+
/*
28+
9 <-- Math.abs(height(left) - height(right)) == 0
29+
/ \
30+
7 13
31+
/\ / \
32+
3 8 10 20
33+
*/
34+
@Test
35+
public void testBinaryTreeIsBalancedEqualSubtreeHeights() {
36+
final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8, 10, 20});
37+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
38+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
39+
}
40+
41+
/*
42+
9 <-- Math.abs(height(left) - height(right)) == 1
43+
/ \
44+
7 13
45+
/\
46+
3 8
47+
*/
48+
@Test
49+
public void testBinaryTreeIsBalancedWithDifferentHeights() {
50+
final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8});
51+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
52+
assertTrue(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
53+
}
54+
55+
/*
56+
9 <-- only left tree exists, Math.abs(height(left) - height(right)) > 1
57+
/
58+
7
59+
/\
60+
3 8
61+
*/
62+
@Test
63+
public void testBinaryTreeNotBalanced() {
64+
final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, null, 3, 8});
65+
assertFalse(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
66+
assertFalse(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
67+
}
68+
69+
/*
70+
9 <-- Math.abs(height(left) - height(right)) > 1
71+
/ \
72+
7 13
73+
/\
74+
3 8
75+
/
76+
11
77+
*/
78+
@Test
79+
public void testBinaryTreeNotBalancedBecauseLeftTreeNotBalanced() {
80+
final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {9, 7, 13, 3, 8, null, null, 11});
81+
assertFalse(CheckIfBinaryTreeBalanced.isBalancedRecursive(root));
82+
assertFalse(CheckIfBinaryTreeBalanced.isBalancedIterative(root));
83+
}
84+
}

0 commit comments

Comments
 (0)