How do you know if a binary tree is in balance?

I am reviewing the class I took at school during the winter vacation. I have a question while studying this tree. I wonder what the best way to find out if the height of the tree is balanced.

I think it'sir

public boolean isBalanced(Node root){
    if(root==null){
        return true; // when the tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

I think we can do it like this. What do you think? What's missing?

algorithm binary java data-structure

2022-09-22 22:05

1 Answers

I think you did it similarly.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

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

I did it like this, so please refer to it.

2022-09-22 22:05

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656