Question

link

Given a binary tree, determine if it is height-balanced.

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.

Stats

Frequency 2
Difficulty 1
Adjusted Difficulty 4
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question for me.

My first code contains many dulicate calls. I have posted it below as an illustration of bad example.

Solution

The solution should make use of the return value from the recursion, and avoid duplication calls. The standard solution is posted below.

Code

First, my initial solution. It takes 30ms more than next code.

public boolean isBalanced(TreeNode root) {
    // my old code re-submit, for speed test
    if (root == null) return true;
    if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
        return false;
    }
    if (! isBalanced(root.left)) return false;
    if (! isBalanced(root.right)) return false;
    return true;
}

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

Second, the standard solution

public boolean isBalanced(TreeNode root) {
    return helper(root) != -1;
}

private int helper(TreeNode node) {
    if (node == null) return 0;
    int a = helper(node.left);
    if (a == -1) return -1;
    int b = helper(node.right);
    if (b == -1) return -1;
    if (Math.abs(a - b) <= 1)
        return Math.max(a, b) + 1;
    else return -1;
}

Updated Oct 29, 2022


public boolean isBalanced(TreeNode root) {
    return helper(root) != -1;
}

private int helper(TreeNode node) {
    if (node == null)
        return 0;

    int a = helper(node.left);
    int b = helper(node.right);

    if (a == -1 || b == -1)
        return -1;

    if (Math.abs(a - b) <= 1)
        return Math.max(a, b) + 1;
    else
        return -1;
}