Как проверить, что бинарное дерево является деревом поиска?

Нужно проверять не только пару «узел — дети», а то, что каждый ключ лежит в допустимом интервале, заданном всеми предками; это делается рекурсией с границами или in-order обходом за O(n) времени и O(h) памяти.

Типичная ошибка

Сравнить узел только с непосредственными детьми. Дерево с корнем 5, левым ребёнком 3 и его правым ребёнком 6 пройдёт такую проверку, хотя 6 в левом поддереве пятёрки нарушает свойство BST.

Решение с границами

/** Узел: { val, left, right }, отсутствующий ребёнок — null */
function isBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isBST(node.left, lo, node.val) && isBST(node.right, node.val, hi);
}

• Спускаясь влево, сужаем верхнюю границу, вправо — нижнюю.
• В Java или C++ нельзя брать Integer.MIN_VALUE как «минус бесконечность»: узел с таким значением даст ложный отказ. Используйте null-границы или long.

Через in-order

In-order обход BST выдаёт строго возрастающую последовательность. Достаточно помнить предыдущее значение и прерваться при первом prev >= cur — без сохранения всего обхода в массив.

Граничные случаи

• Дубликаты: заранее договоритесь, разрешены ли они и в какую сторону идут; от этого зависит строгость сравнений.
• Вырожденное дерево глубиной 10⁵ переполнит стек рекурсии — нужен итеративный обход.

Коротко для собеседования

Проверять надо не пару «родитель — ребёнок», а то, что каждый узел попадает в интервал, заданный всеми предками: рекурсией с границами или in-order обходом с проверкой строгого возрастания. Частые ошибки — сравнивать узел только с детьми и брать минимальный int как «минус бесконечность».