Given a binary tree, determine if it is height-balanced. NOTE: a balanced binary tree is defined as the following:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

We can use Divide and Conquer method on this question. The solution is shown as below:

    public boolean isBalanced(TreeNode root) {

        if(root == null){
            return true;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);  
    }

    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

We need to make sure the height difference between left and right node is no more than 1. This is not a very optimal solution because it bascially checks every single node to make sure the height is balanced. The overall runtime is O(n²).

There is another method provided by jiuzhang.com which uses ResultType to hold the isBalanced and maxDepth variables.

class ResultType {
    public boolean isBalanced;
    public int maxDepth;
    public ResultType(boolean isBalanced, int maxDepth) {
        this.isBalanced = isBalanced;
        this.maxDepth = maxDepth;
    }
}

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root).isBalanced;
    }
    
    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, 0);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        // subtree not balance
        if (!left.isBalanced || !right.isBalanced) {
            return new ResultType(false, -1);
        }
        
        // root not balance
        if (Math.abs(left.maxDepth - right.maxDepth) > 1) {
            return new ResultType(false, -1);
        }
        
        return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1);
    }
}

Set the ResultType to (false, -1) when the left or right tree is not balanced or the max depth is greater than 1.

---

So, which one is easier to learn? Well, it doesn't really matter as long as you get the gist of it! Good luck coding!

Post was published on 7 Jan 2020, last updated on 7 Jan 2020.

Like the content? Support the author by paypal.me!