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) &gt; 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) { // &lt;-- Useless
        return 0;              // &lt;-- Useless
    }                          // &lt;-- 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) &gt; 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) &gt; 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