Check if a binary tree is balanced

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 {

private TreeNode root;

public CheckBalancedTree(List items) {
create(items);
}

private void create (List items) {
if (items.size() == 0) { throw new IllegalArgumentException("The list is empty."); }

root = new TreeNode<>(items.get(0));

final Queue> queue = new LinkedList<>();
queue.add(root);

final int half = items.size() / 2;

for (int i = 0; i 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.get(right));
queue.add(current.right);
}
}
}
}

// create a binary tree.
private static class TreeNode {
private TreeNode left;
private E item;
private TreeNode 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 Tre

-
From an algorithmic point of view TreeData actually uses \$\mathcal{O}(1)\$ space. However, the statement that it gets garbage collected when the reference to it no longer exists is not correct. It can be garbage collected much later(or even never).

-
About code style. There are some inconsistencies in your code. When the if statement body consists of an only one statement, sometimes you put on the same line without using brackets, like here: if (node == null) return new TreeData(-1, true);, but sometimes you do start a new line and use brackets:

if (tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
    return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
}

I would recommend using the latter(or, at least, stick to one style, do not mix them).

-
The amount of blank lines inside one method seems to be too big.

root = new TreeNode<>(items.get(0));

final Queue> queue = new LinkedList<>();
queue.add(root);

final int half = items.size() / 2;

for (int i = 0; i < half; i++) {

It looks better this way:

root = new TreeNode<>(items.get(0));
final Queue> queue = new LinkedList<>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {

-
It is also a good practice to write comments for all public classes and methods(they should tell what instances of this class represent or what this method does).

StackExchange Code Review Q#80056, answer score: 4