Looking for code-review, optimizations and best practices. This question is attributed to geeksforgeeks.
NOTE: Please help me verify space complexity, as I am creating TreeData
objects in recursion. I believe it is \$\mathcal{O}(1)\$. Ignore the space-complexity of stack frames. Looking only for space occupied by TreeData. At any point there are only 3 TreeData objects. As frame is popped, the TreeData gets garbage collected. Please verify.
public class CheckBalancedTree<E> {
private TreeNode<E> root;
public CheckBalancedTree(List<E> items) {
create(items);
}
private void create (List<E> items) {
if (items.size() == 0) { throw new IllegalArgumentException("The list is empty."); }
root = new TreeNode<>(items.get(0));
final Queue<TreeNode<E>> queue = new LinkedList<>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode<E> current = queue.poll();
int left = 2 * i + 1;
int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode<>(items.get(left));
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<>(items.get(right));
queue.add(current.right);
}
}
}
}
// create a binary tree.
private static class TreeNode<E> {
private TreeNode<E> left;
private E item;
private TreeNode<E> right;
TreeNode(E item) {
this.item = item;
}
}
private static class TreeData {
private int height;
private boolean isBalanced;
TreeData(int height, boolean isBalanced) {
this.height = height;
this.isBalanced = isBalanced;
}
}
public boolean checkIfBalanced() {
if (root == null) {
throw new IllegalStateException();
}
return checkBalanced(root).isBalanced;
}
public TreeData checkBalanced(TreeNode<E> node) {
if (node == null) return new TreeData(-1, true);
TreeData tdLeft = checkBalanced(node.left);
if (!tdLeft.isBalanced) return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.
TreeData tdRight = checkBalanced(node.right);
if (tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
}
return new TreeData(-1, false); // if boolean value is false, then no need to return the correct value for height.
}
}
public class CheckBalancedTreeTest {
@Test
public void testLeftSkewed() {
/* 1
* /
* 2
* /
* 3
*/
Integer[] leftSkewed = {1, 2, null, 3, null, null, null};
CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(leftSkewed));
assertFalse(cbt.checkIfBalanced());
}
@Test
public void testRightSkewed() {
/* 1
* \
* 2
* \
* 3
*/
Integer[] rightSkewed = {1, null, 2, null, null, null, 3 };
CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(rightSkewed));
assertFalse(cbt.checkIfBalanced());
}
@Test
public void testSuccessCase() {
/*
* 1
* / \
* 2 3
* /\
* 4 5
*/
Integer[] successCase = {1, 2, 3, 4, 5, null, null};
CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(successCase));
assertTrue(cbt.checkIfBalanced());
}
@Test
public void testFailureCase() {
/*
* 1
* / \
* 2 3
* / \
* 4 5
* / \
* 6 7
*/
Integer[] failure = {1, 2, 3, 4, 5, null, null, null, null, 6, 7, null, null};
CheckBalancedTree<Integer> cbt = new CheckBalancedTree<>(Arrays.asList(failure));
assertFalse(cbt.checkIfBalanced());
}
}