Balanced Binary Tree

There are some things that smell about this code, for instance multiple checking, length both returning value and changing some other variable. But I can't for the moment figure how to make it nicer, or if that's even possible. Converting it to stack-based solution seems to be making it a bit too-complicated.

Please provide a review of this code, what do you think could be improved, if possible, both in terms of readability and performance or possible problems.

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
boolean isBalanced = true;

public boolean isBalanced(TreeNode root) {
length(root);
return isBalanced;
}

public int length(TreeNode a) {
if (a == null) {
return 0;
}
if (isBalanced == false) {
return 0;
}
int x = length(a.left);
if (isBalanced == false) {
return 0;
}
int y = length(a.right);
if (isBalanced == false) {
return 0;
}
if (Math.abs(x - y) > 1) {
isBalanced = false;
return 0;
}
return Math.max(x, y) + 1;
}
}

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

What really hurts this code is that the length method wants to return two things at once: the branch depth, and a global isBalanced status.

To do that, the author returned branch depth directly, and isBalanced as a global variable. I'm all against global variables, but I must admit this does work. I think there's a useless line of code, though:

public int length(TreeNode a) {
if (a == null) {
return 0;
}
if (isBalanced == false) { // <-- Useless
return 0;              // <-- Useless
}                          // <-- Useless

Otherwise, it's not all too bad. It uses a magic value to early return from recursion.

Another possibility is to throw a UnbalancedException - don't kill me right away, throwing exceptions upon rencountering abnormal situations is not evil! If it's not happening too often, it's quite reasonable, and makes for a much cleaner design:

public class Solution {
public boolean isBalanced(TreeNode root) {
try{
length(root);
return true;
} catch(UnbalancedException unbalanced){
return false;
}
}

public int length(TreeNode a) throws UnbalancedException{
if (a == null) {
return 0;
}
int x = length(a.left);
int y = length(a.right);
if (Math.abs(x - y) > 1) {
throw new UnbalancedException();
}
return Math.max(x, y) + 1;
}
}

With this design, you've gained a length method that actually works!

The most JAVA possibility - suposedly cleaner, but that I like the least - is to create a ad-hoc Response object like a BalancedStatus:

public class BalancedStatus {
private final boolean isBalanced;
private int depth;
// Getters, and constructors here
}

And :

public class Solution {
public boolean isBalanced(TreeNode root) {
BalancedStatus rootStatus = length(root);
return rootStatus.isBalanced();
}
public BalancedStatus length(TreeNode a) {
if (a == null) {
return new BalancedStatus();
}
BalancedStatus x = length(a.left);
if(!x.isBalanced()){
return new BalancedStatus(false);
}
BalancedStatus y = length(a.right);
if(!y.isBalanced()){
return new BalancedStatus(false);
}
if (Math.abs(x - y) > 1) {
return new BalancedStatus(false);
}
return new BalancedStatus(Math.max(x, y) + 1);
}
}

But I don't like this because it instantiates two Objects per recursion level...

Finally, we could axe the recursion and use iteration instead, but since this is a branching recursion we'd need a List (Queue?) to track the progress.
Pros:

• No recursion (no stack overflow etc.)
• Easy early exit (just return)

Cons:

• Requires to setup a List of nodes to do
• Requires to be able to link back from node to parent (Map?) to propagate depth
• the length method does not work, since you can't retrieve the lenght when the tree is unbalanced. It's crucial to understand how the tree needs to be rotated when it's unbalanced and that is only possible when you know the depths of the relevant subtrees. The BalanceStatus class is an interesting idea, it suffers from a different problem though. It would be much easier to store the balance status inside the tree nodes and propagate it back the insertion recursion stack including performing rotations where necessary ... This would completely eliminate the need for the global variable. – Vogel612 Oct 21 '16 at 10:41
• Good points. I simply proposed a method of returning length, on the assumption that an unbalanced tree is invalid / corrected right away and should not be encountered. But that may not be OP's use-case. About storing the isBalanced status on the Node, I also assumed OP wanted an external solution (maybe Node was not extensible?), otherwise both length() and isBalanced() should be methods of Node, and not of Solution! – MrBrushy Oct 21 '16 at 11:55