PHP: Построение двоичного дерева

Двоичное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

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

src/Node.php

Реализуйте метод insert($key), который выполняет добавление узла, формируя правильное двоичное дерево.

Примеры

<?php

use App\Node;

$tree = new Node();
$tree->insert(9);
$tree->insert(17);
$tree->insert(4);
$tree->insert(3);
$tree->insert(6);

$tree->getKey(); // 9
$tree->getLeft()->getKey(); // 4
$tree->getRight()->getKey(); // 17
$tree->getLeft()->getLeft()->getKey(); // 3
$tree->getLeft()->getRight()->getKey(); // 6

Подсказки

• Двоичное дерево
• Двоичное дерево поиска