Ошибка утверждения при проверке сбалансированности дерева

Question

У меня есть двоичное дерево, и я хочу проверить, сбалансировано ли дерево. У меня есть следующий код:

public boolean isBalanced(){
        return balanced(root);
    }

    public boolean balanced(Node current){
        int leftHeight;

        int rightHeight;

        if(current == null){
            return true;
        }
        leftHeight = height(current.left);
        rightHeight = height(current.right);

        if(leftHeight - rightHeight <= 1){
            return true;
        }

        return false;
    }

    int height(Node node) 
    { 
        /* base case tree is empty */
        if (node == null) 
            return 0; 

        /* If tree is not empty then height = 1 + max of left 
         height and right heights */
        return 1 + Math.max(height(node.left), height(node.right)); 
    } 

Тест выдает ошибку java.lang.AssertionError, но не более подробную информацию. Я не могу понять, откуда взялась эта ошибка.

Answer 1

Согласно википедии , определение сбалансированного двоичного дерева - A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

В вашем коде вы проверяете

if(leftHeight - rightHeight <= 1){
      return true;
}

Что если leftHeight = 0 и rightHeight=2? Ваш код вернет true как (0-2) = -2 and -2 <= 1. Вы должны проверить абсолютную разницу между высотой левого поддерева и высотой правого поддерева.