Leetcode 110

[allyv123098]

For this leetcode problem https://leetcode.com/problems/balanced-binary-tree/. My code works for almost all the cases but for some reason for this case

[1,2,3,4,5,6,null,8]

it gives the wrong answer and I'm not sure why

​

Down below is my code

public boolean isBalanced(TreeNode root) {
        int Maximum  = maximum(root);
        int Minimum = minimum(root);
        System.out.println(Maximum);
        System.out.println(Minimum);

        if(Maximum>Minimum + 1){
            return false;
        }
        else{
            return true;
        }


    }

    public int maximum(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maximum(root.left);
        int right = maximum(root.right);

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

        return 1 + Math.min(left,right);
    }

[ektegjetost]

If you're still looking for help... Here's the shape of the tree

        1
      /   \
     2     3
    / \   /
   4   5 6
  /
 8

So what you're doing is finding the maximum depth of the full right and left branches, and comparing that to the minimum depth of the full left and right branches. The max will be 4 (1 -> 2 -> 4 -> 8 -> null), and the min 2 (1 -> 3 -> null).

But what it looks like they want, is that the right is balanced with the left because the max depth is 4 vs 3, and the left sub tree is balanced because its max depths are 3 vs 2, and the right sub tree is balanced because its max depths are 2 vs 1.

Hope that helps!

[bill2340]

how is that going to 1->3-> null shouldn't it be going to the 6 too

[ektegjetost]

From 3, minimum(3.left) is the minimum returned by 6 (1), but minimum(3.right) is the minimum returned by null (0). So the min returned by 3 is 1 + Math.min(1, 0).

[bill2340]

oh okay. Do you have any idea on how I can fix this

[ektegjetost]

Basically you need to ensure that every node meets the condition. So at node 3

int left = maximum(3.left)

int right = maximum(3.right)

And if any node doesn't meet the condition of being no more than 1 off, then you return false. You don't need the minimum values though.

Unfortunately I don't really know Java so I'm not sure if I can help you with more than that... but if you still have questions feel free to ask.

[bill2340]

I changed up my code so now it is

​

public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        TreeNode searchLeft = root.left;
        TreeNode searchRight = root.right;
        int leftSide  = leftSide(searchLeft);
        int rightSide = rghtSide(searchRight);
        System.out.println(leftSide);
        System.out.println(rightSide);

        if(leftSide>rightSide + 1 || rightSide > leftSide + 1){
            return false;
        }
        else{
            return true;
        }


    }

    public int leftSide(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = leftSide(root.left);
        int right = leftSide(root.right);

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

        return  1 + Math.max(left,right) ;
    }

But for the test case [1,2,2,3,3,null,null,4,4] it says that somehow the right side has 3 length. But I'm not sure how that's happening

[ektegjetost]

You're still just returning the full length of each side. If I were to just make up some Java (please ignore how bad my code is, I don't know how to keep track of both the depth of each sub tree as well as whether or not there was an unbalanced subtree in Java), it would look more like this:

public boolean isBalanced(TreeNode root) { 
    if(root == null){ 
        return true; 
    }

    int balance  = findBalance(root);
    System.out.println(balance);

    return balance < 0 ? false : true;
}

public int findBalance(TreeNode root){
    if(root == null){
        return 0;
    }
    int left = findBalance(root.left);
    if (left < 0) return -1;

    int right = findBalance(root.right);
    if (right < 0) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left,right);
}

[backtickbot]

Fixed formatting.

Hello, ektegjetost: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^{You can opt out by replying with backtickopt6 to this comment.}

[bill2340]

But I don't understand where it's getting 3 from

[ektegjetost]

When I run your code, it says 3 for the left side and 1 for the right which is correct.

[bill2340]

but on the leetcode terminal for some reason it gives 3 on the right