Обсуждение участника:Novik

Проверка двоичного дерева

Дано произвольное двоичное дерево и необходимо узнать является ли оно деревом поиска. Чтобы дерево было деревом поиска достаточно выполнение следующих условий для всех вершин:

• правое и левое поддеревья являются деревьями поиска,
• максимум в левом поддереве меньше значения в текущей вершине, а минимум в правом больше.

Псевдокод:

boolean isSearchTree(Node v):
    if (v.l == null && v.r == null)
        v.max = v.val;
        v.min = v.val;
        return true;
    if (isSearchTree(v.l) && isSearchTree(v.r) && v.l.max < v.val && v.r.min > v.val)
        v.max = v.r.max;
        v.min = v.l.min;
        return true;
    else
        return false;

Поиск максимального поддерева, являющегося целым деревом поиска

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