Нахождение высоты двоичного дерева

Question

Я написал следующий код для определения высоты двоичного дерева, это неверно, это не соответствует тестовым случаям, но почему это неправильно, как логически доказать, что это неправильно?

// НЕПРАВИЛЬНЫЙ КОД

public static int height(Node root) {
          if(root != null){
            if(root.left != null && root.right != null){   
              return Math.max(height(root.left), height(root.right)) + 1;
            }else if(root.left != null){
               return height(root.left);  
            }else{
               return height(root.right);
            } 
          }
        return 0;  
    }

Тогда как этот следующий код правильный !!

// ПРАВИЛЬНЫЙ РАБОЧИЙ КОД

public static int height(Node root) {
    if(root != null){
        if(root.left != null || root.right != null){   
          return Math.max(height(root.left), height(root.right)) + 1;
        }
      }
    return 0;  
}

В чем большая разница между двумя кодами, делающая один из них правильным, а другой неправильным?

Для ясности здесь добавлен код класса для узла.

class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

И это лог c для вставки узла в двоичное дерево.

public static Node insert(Node root, int data) {
    if(root == null) {
        return new Node(data);
    } else {
        Node cur;
        if(data <= root.data) {
            cur = insert(root.left, data);
            root.left = cur;
        } else {
            cur = insert(root.right, data);
            root.right = cur;
        }
        return root;
    }

Answer 1

Во втором и третьем случаях (только левый узел или только правый узел) вы не добавляете его для учета текущего узла.

Кстати, ваш код также имеет потенциальную ошибку, так как left и right могут быть null. Ваша функция height может обрабатывать null, поэтому на самом деле ни одна из этих проверок не требуется, за исключением проверки в первой строке самой функции height. Но если важно проверить наличие null во втором случае, то вам следует проверить и null и в третьем случае.