Balanced Binary Tree

Question

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.

Answer 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