Skip to content

Commit 664bcf4

Browse files
iccowaniccowan
authored
Check if Binary Tree is Balanced Closes TheAlgorithms#2719 (TheAlgorithms#2732)
1 parent f9e4201 commit 664bcf4

File tree

1 file changed

+274
-0
lines changed

1 file changed

+274
-0
lines changed

‎DataStructures/Trees/CheckIfBinaryTreeBalanced.java

Lines changed: 274 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,274 @@
1+
package DataStructures.Trees;
2+
3+
import java.util.Stack;
4+
import java.util.HashMap;
5+
6+
/**
7+
* This class will check if a BinaryTree is balanced.
8+
* A balanced binary tree is defined as a binary tree where
9+
* the differenced in height between the left and right
10+
* subtree of each node differs by at most one.
11+
*
12+
* This can be done in both an iterative and recursive
13+
* fashion. Below, `isBalancedRecursive()` is
14+
* implemented in a recursive fashion, and
15+
* `isBalancedIterative()` is implemented in an
16+
* iterative fashion.
17+
*
18+
* @author [Ian Cowan](https://github.com/iccowan)
19+
*/
20+
public class CheckIfBinaryTreeBalanced {
21+
22+
/**
23+
* This class implements the BinaryTree for these algorithms
24+
*/
25+
class BinaryTree {
26+
/** The root node of the binary tree */
27+
BTNode root = null;
28+
}
29+
30+
/**
31+
* This class implements the nodes for the binary tree
32+
*/
33+
class BTNode {
34+
/** The value of the node */
35+
int value;
36+
37+
/** The left child of the node */
38+
BTNode left = null;
39+
40+
/** The right child of the node */
41+
BTNode right = null;
42+
43+
/** Constructor */
44+
BTNode (int value) {
45+
this.value = value;
46+
}
47+
}
48+
49+
/**
50+
* Recursive is BT balanced implementation
51+
*
52+
* @param binaryTree The binary tree to check if balanced
53+
*/
54+
public boolean isBalancedRecursive(BinaryTree binaryTree) {
55+
// Create an array of length 1 to keep track of our balance
56+
// Default to true. We use an array so we have an efficient mutable object
57+
boolean[] isBalanced = new boolean[1];
58+
isBalanced[0] = true;
59+
60+
// Check for balance and return whether or not we are balanced
61+
isBalancedRecursive(binaryTree.root, 0, isBalanced);
62+
return isBalanced[0];
63+
}
64+
65+
/**
66+
* Private helper method to keep track of the depth and balance during
67+
* recursion. We effectively perform a modified post-order traversal where
68+
* we are looking at the heights of both children of each node in the tree
69+
*
70+
* @param node The current node to explore
71+
* @param depth The current depth of the node
72+
* @param isBalanced The array of length 1 keeping track of our balance
73+
*/
74+
private int isBalancedRecursive(BTNode node, int depth, boolean[] isBalanced) {
75+
// If the node is null, we should not explore it and the height is 0
76+
// If the tree is already not balanced, might as well stop because we
77+
// can't make it balanced now!
78+
if (node == null || ! isBalanced[0])
79+
return 0;
80+
81+
// Visit the left and right children, incrementing their depths by 1
82+
int leftHeight = isBalancedRecursive(node.left, depth + 1, isBalanced);
83+
int rightHeight = isBalancedRecursive(node.right, depth + 1, isBalanced);
84+
85+
// If the height of either of the left or right subtrees differ by more
86+
// than 1, we cannot be balanced
87+
if (Math.abs(leftHeight - rightHeight) > 1)
88+
isBalanced[0] = false;
89+
90+
// The height of our tree is the maximum of the heights of the left
91+
// and right subtrees plus one
92+
return Math.max(leftHeight, rightHeight) + 1;
93+
}
94+
95+
/**
96+
* Iterative is BT balanced implementation
97+
*/
98+
public boolean isBalancedIterative(BinaryTree binaryTree) {
99+
// Default that we are balanced and our algo will prove it wrong
100+
boolean isBalanced = true;
101+
102+
// Create a stack for our post order traversal
103+
Stack<BTNode> nodeStack = new Stack<BTNode>();
104+
105+
// For post order traversal, we'll have to keep track of where we
106+
// visited last
107+
BTNode lastVisited = null;
108+
109+
// Create a HashMap to keep track of the subtree heights for each node
110+
HashMap<BTNode, Integer> subtreeHeights = new HashMap<BTNode, Integer>();
111+
112+
// We begin at the root of the tree
113+
BTNode node = binaryTree.root;
114+
115+
// We loop while:
116+
// - the node stack is empty and the node we explore is null
117+
// AND
118+
// - the tree is still balanced
119+
while (! (nodeStack.isEmpty() && node == null) && isBalanced) {
120+
// If the node is not null, we push it to the stack and continue
121+
// to the left
122+
if (node != null) {
123+
nodeStack.push(node);
124+
node = node.left;
125+
// Once we hit a node that is null, we are as deep as we can go
126+
// to the left
127+
} else {
128+
// Find the last node we put on the stack
129+
node = nodeStack.peek();
130+
131+
// If the right child of the node has either been visited or
132+
// is null, we visit this node
133+
if (node.right == null || node.right == lastVisited) {
134+
// We assume the left and right heights are 0
135+
int leftHeight = 0;
136+
int rightHeight = 0;
137+
138+
// If the right and left children are not null, we must
139+
// have already explored them and have a height
140+
// for them so let's get that
141+
if (node.left != null)
142+
leftHeight = subtreeHeights.get(node.left);
143+
144+
if (node.right != null)
145+
rightHeight = subtreeHeights.get(node.right);
146+
147+
// If the difference in the height of the right subtree
148+
// and left subtree differs by more than 1, we cannot be
149+
// balanced
150+
if (Math.abs(rightHeight - leftHeight) > 1)
151+
isBalanced = false;
152+
153+
// The height of the subtree containing this node is the
154+
// max of the left and right subtree heighs plus 1
155+
subtreeHeights.put(node, Math.max(rightHeight, leftHeight) + 1);
156+
157+
// We've now visited this node, so we pop it from the stack
158+
nodeStack.pop();
159+
lastVisited = node;
160+
161+
// Current visiting node is now null
162+
node = null;
163+
// If the right child node of this node has not been visited
164+
// and is not null, we need to get that child node on the stack
165+
} else {
166+
node = node.right;
167+
}
168+
}
169+
}
170+
171+
// Return whether or not the tree is balanced
172+
return isBalanced;
173+
}
174+
175+
/**
176+
* Generates the following unbalanced binary tree for testing
177+
* 0
178+
* / \
179+
* / \
180+
* 0 0
181+
* / / \
182+
* / / \
183+
* 0 0 0
184+
* / \
185+
* / \
186+
* 0 0
187+
* /
188+
* /
189+
* 0
190+
*/
191+
private BinaryTree buildUnbalancedTree() {
192+
BinaryTree tree = new BinaryTree();
193+
tree.root = new BTNode(0);
194+
195+
BTNode root = tree.root;
196+
root.left = new BTNode(0);
197+
root.right = new BTNode(0);
198+
199+
BTNode left = root.left;
200+
BTNode right = root.right;
201+
202+
left.left = new BTNode(0);
203+
right.left = new BTNode(0);
204+
right.right = new BTNode(0);
205+
right.left.right = new BTNode(0);
206+
207+
left = left.left;
208+
left.left = new BTNode(0);
209+
left.left.left = new BTNode(0);
210+
left.left.left.left = new BTNode(0);
211+
212+
return tree;
213+
}
214+
215+
/**
216+
* Generates the following balanced binary tree for testing
217+
* 0
218+
* / \
219+
* / \
220+
* 0 0
221+
* / \ / \
222+
* / 0 / \
223+
* 0 0 0
224+
* / /
225+
* / /
226+
* 0 0
227+
*/
228+
private BinaryTree buildBalancedTree() {
229+
BinaryTree tree = new BinaryTree();
230+
tree.root = new BTNode(0);
231+
232+
BTNode root = tree.root;
233+
root.left = new BTNode(0);
234+
root.right = new BTNode(0);
235+
236+
BTNode left = root.left;
237+
BTNode right = root.right;
238+
239+
left.left = new BTNode(0);
240+
left.right = new BTNode(0);
241+
right.left = new BTNode(0);
242+
right.right = new BTNode(0);
243+
244+
right.right.left = new BTNode(0);
245+
246+
left.left.left = new BTNode(0);
247+
248+
return tree;
249+
}
250+
251+
/**
252+
* Main
253+
*/
254+
public static void main(String[] args) {
255+
// We create a new object to check the binary trees for balance
256+
CheckIfBinaryTreeBalanced balanceCheck = new CheckIfBinaryTreeBalanced();
257+
258+
// Build a balanced and unbalanced binary tree
259+
BinaryTree balancedTree = balanceCheck.buildBalancedTree();
260+
BinaryTree unbalancedTree = balanceCheck.buildUnbalancedTree();
261+
262+
// Run basic tests on the algorithms to check for balance
263+
boolean isBalancedRB = balanceCheck.isBalancedRecursive(balancedTree); // true
264+
boolean isBalancedRU = balanceCheck.isBalancedRecursive(unbalancedTree); // false
265+
boolean isBalancedIB = balanceCheck.isBalancedIterative(balancedTree); // true
266+
boolean isBalancedIU = balanceCheck.isBalancedIterative(unbalancedTree); // false
267+
268+
// Print the results
269+
System.out.println("isBalancedRB: " + isBalancedRB);
270+
System.out.println("isBalancedRU: " + isBalancedRU);
271+
System.out.println("isBalancedIB: " + isBalancedIB);
272+
System.out.println("isBalancedIU: " + isBalancedIU);
273+
}
274+
}

0 commit comments

Comments
 (0)