Php: Сбалансированное двоичное дерево

Особенность структуры двоичного дерева даёт хороший прирост к эффективности при поиске нужного значения. Для этого нужно, чтобы двоичное дерево было сбалансированным. То есть необходимо построить дерево так, чтобы общее количество узлов в левом и правом поддеревьях было примерно одинаковым для любого узла дерева.

src/Node.php

Реализуйте метод isBalanced(), который проверяет дерево на сбалансированность. Он возвращает true, если количество узлов в левом и правом поддеревьях каждого узла отличается не более, чем на 2. В ином случае метод должен вернуть false.

Сбалансированное дерево

Несбалансированное дерево

В узле 5 количество узлов в левом поддереве равно 4, а в правом — 1. Разница составляет 3. Это больше, чем максимально допустимая разница по условию задачи (2).

Примеры

<?php

use App\Node;

$tree1 = new Node(
    4,
    new Node(
        3,
        new Node(2)
    )
);

$tree1->isBalanced(); // true

$tree2 = new Node(
    4,
    new Node(
        3,
        new Node(
            2,
            new Node(1)
        )
    )
);

$tree2->isBalanced(); // false