Введение в бинарное дерево поиска

Бинарное дерево поиска (BST) — это обычное бинарное дерево, но с одним правилом: у каждого узла левый ребёнок меньше, а правый больше.

У 8 слева 3 (меньше), справа 10 (больше). У 3 слева 1 (меньше), справа 6 (больше). И так для каждого узла в дереве.

Причём правило распространяется не только на прямых детей, а на всё поддерево. Например, узел 6 находится левее 8 и правее 3 — значит все узлы в этом поддереве должны быть строго 3 < node.val < 8. Если хотя бы один нарушает границы — это уже не BST.

Из этого правила следует простое свойство: если от любого узла идти всё время влево — придём к наименьшему элементу в поддереве, если вправо — к наибольшему.

Переходи к задаче и попробуй решить её, используя это свойство.