UniLecs #Task. Trim BST

Задача: дано бинарное дерево поиска и значение min, max. Необходимо обрезать дерево таким образом, чтобы все его элемементы лежали в диапазоне [min, max]. Обрезка дерева не должна менять относительную структуру элементов, которые останутся в дереве (т.е. потомок любого узла должен оставаться потомком).

Входные данные: root — корень бинарного дерева поиска, 0 <= min<max <= 100.

Вывод: обрезанное дерево.

Примеры:

1. Min = 1; Max = 2;

Input

Output

2. Min = 1; Max = 3;

Input

Output

Разбор

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

Двоичное дерево поиска — это двоичное дерево, для которого выполняются следующие дополнительные условия:

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

Алгоритм

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

• Если мы дошли до крайнего узла, т.е. node == null, возвращаем node.
• Если значение текущего узла меньше Min, то очевидно, что все узлы левого поддерева меньше чем Min. Тогда рекурсивно запускаем функцию только для правого поддерева.
• Если значение текущего узла больше Max, то очевидно, что все узлы правого поддерева больше чем Max. Тогда рекурсивно запускаем функцию только для левого поддерева.
• Если значение текущего узла в пределах диапазона, то запускаем функцию для левого и правого поддерева.
• Возвращаем текущий узел.

Детали алгогритма смотрите в коде.

Реализация

C#

https://gist.github.com/unilecs/7fe2be359ef93ac52d4f3b65447714ef

Play-test

https://dotnetfiddle.net/5vAVAL