PHP: Агрегация в двоичном дереве

В данном испытании мы будем использовать двоичное дерево, и выполнять агрегацию данных.

src/Node.php

Реализуйте следующие методы в классе:

• getCount() — возвращает количество узлов в дереве.
• getSum() — возвращает сумму всех ключей дерева.
• toArray() — возвращает одномерный массив содержащий все ключи.
• toString() — возвращает строковое представление дерева.
• every($fn) — проверяет, удовлетворяют ли все ключи дерева условию, заданному в передаваемой функции.
• some($fn) - проверяет, удовлетворяет ли какой-либо ключ дерева условию, заданному в передаваемой функции.

При обходе дерева нужно использовать порядок слева-направо. То есть вначале обрабатываем ключ узла, затем ключ левого ребёнка, после чего ключ правого ребёнка.

Примеры

<?php

use App\Node;

$tree = new Node(
    9,
    new Node(
        4,
        new Node(3),
        new Node(
            6,
            new Node(5),
            new Node(7)
        )
    ),
    new Node(
        17,
        null,
        new Node(
            22,
            null,
            new Node(23)
        )
    )
);

$tree->getCount(); // 9
$tree->getSum(); // 96
$tree->toArray(); // [9, 4, 3, 6, 5, 7, 17, 22, 23]
$tree->toString(); // '(9, 4, 3, 6, 5, 7, 17, 22, 23)'

$tree->every(fn($key) => $key <= 23); // true
$tree->every(fn($key) => $key < 10); // false
$tree->some(fn($key) => $key < 4); // true
$tree->some(fn($key) => $key > 24); // false

Подсказки

• Двоичное дерево
• Для реализации каждого из методов потребуется выполнить обход всех узлов дерева.
• Вспомните принцип работы метода array_reduce.