forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCheckIfBinaryTreeBalanced.java
More file actions
274 lines (230 loc) · 9.35 KB
/
CheckIfBinaryTreeBalanced.java
File metadata and controls
274 lines (230 loc) · 9.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
package DataStructures.Trees;
import java.util.Stack;
import java.util.HashMap;
/**
* 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 right
* subtree of each node differs by at most one.
*
* 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.
*
* @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
*/
public boolean isBalancedRecursive(BinaryTree binaryTree) {
// 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
boolean[] isBalanced = new boolean[1];
isBalanced[0] = true;
// Check for balance and return whether or not we are balanced
isBalancedRecursive(binaryTree.root, 0, isBalanced);
return isBalanced[0];
}
/**
* Private helper method to keep track of the depth and balance during
* 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 isBalanced The array of length 1 keeping track of our balance
*/
private int isBalancedRecursive(BTNode 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!
if (node == null || ! isBalanced[0])
return 0;
// Visit the left and right children, incrementing their depths by 1
int leftHeight = isBalancedRecursive(node.left, depth + 1, isBalanced);
int rightHeight = isBalancedRecursive(node.right, depth + 1, isBalanced);
// If the height of either of the left or right subtrees differ by more
// than 1, we cannot be balanced
if (Math.abs(leftHeight - rightHeight) > 1)
isBalanced[0] = false;
// The height of our tree is the maximum of the heights of the left
// and right subtrees plus one
return Math.max(leftHeight, rightHeight) + 1;
}
/**
* Iterative is BT balanced implementation
*/
public boolean isBalancedIterative(BinaryTree binaryTree) {
// 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>();
// For post order traversal, we'll have to keep track of where we
// visited last
BTNode lastVisited = null;
// Create a HashMap to keep track of the subtree heights for each node
HashMap<BTNode, Integer> subtreeHeights = new HashMap<BTNode, Integer>();
// We begin at the root of the tree
BTNode node = binaryTree.root;
// We loop while:
// - the node stack is empty and the node we explore is null
// AND
// - the tree is still balanced
while (! (nodeStack.isEmpty() && node == null) && isBalanced) {
// If the node is not null, we push it to the stack and continue
// to the left
if (node != null) {
nodeStack.push(node);
node = node.left;
// Once we hit a node that is null, we are as deep as we can go
// to the left
} else {
// Find the last node we put on the stack
node = nodeStack.peek();
// If the right child of the node has either been visited or
// is null, we visit this node
if (node.right == null || node.right == lastVisited) {
// We assume the left and right heights are 0
int leftHeight = 0;
int rightHeight = 0;
// If the right and left children are not null, we must
// have already explored them and have a height
// for them so let's get that
if (node.left != null)
leftHeight = subtreeHeights.get(node.left);
if (node.right != null)
rightHeight = subtreeHeights.get(node.right);
// If the difference in the height of the right subtree
// and left subtree differs by more than 1, we cannot be
// balanced
if (Math.abs(rightHeight - leftHeight) > 1)
isBalanced = false;
// The height of the subtree containing this node is the
// max of the left and right subtree heighs plus 1
subtreeHeights.put(node, Math.max(rightHeight, leftHeight) + 1);
// We've now visited this node, so we pop it from the stack
nodeStack.pop();
lastVisited = node;
// Current visiting node is now null
node = null;
// If the right child node of this node has not been visited
// and is not null, we need to get that child node on the stack
} else {
node = node.right;
}
}
}
// Return whether or not 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);
}
}