3

https://leetcode.com/problems/balanced-binary-tree/

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.

public class Solution {
    public boolean isBalanced(TreeNode root) {
        
        int ret = getLevel(root);
        if(ret < 0)
            return false;
        
        return true;
        
    }
    public int getLevel(TreeNode node) {

        if(node == null)
            return 0;

        int l = getLevel(node.left);
        int r = getLevel(node.right);
        if(Math.abs(l - r) > 1)
            return -99;
            
        return Math.max(l + 1, r + 1);
    }
}

This code is Accepted. However if I replace -99 with Integer.MIN_VALUE, my code fails. What's the bug?

e.g.

Input: [1,2,null,3,null,4,null,5]

Output: true

Expected: false

0

2 Answers 2

3

Your code is failing because of integer arithmetic which is overflowing. The following code snippet will demonstrate this:

int val = Integer.MIN_VALUE;
System.out.println(val);
val -= 3;
System.out.println(val);

Output:

-2147483648
2147483645

Now consider what is happening in your actual code:

int l = getLevel(node.left);
// l == -2147483648 == Integer.MIN_VALUE assuming your base case is hit
int r = getLevel(node.right);
// assuming positive r, then Math.abs() will return a massively positive number
if (Math.abs(l - r) > 1)
        return -99;

In other words, the above if statement will be firing true when it really should have fired false.

Solution:

If you modify the getLevel() method to the following, you should skirt the problems you are having:

public int getLevel(TreeNode node) {
    if(node == null)
        return 0;

    int l = getLevel(node.left);
    int r = getLevel(node.right);
    if ( (l < 0 ^ r < 0) || Math.abs(l - r) > 1) {
        // you can simply return -1 here, since an actual
        // level should never have a negative value
        return -1;
    }
    else {
        return Math.max(l + 1, r + 1);
    }
}
1
  • This is completely oposite, it returns false when it should return true. But it happens only in very special situations,see my answer. Your case doesn't hurt actually. Dec 16, 2015 at 5:24
0

It may fail under some circumstances due to overflow. If l is zero and r is Integer.MIN_VALUE, l-r is actually negative because it overflows. As a result, the condition will fail and the next statement returns max of MIN_VALUE+1 and zero+1.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.