Задача Validate Binary Search Tree — одна из тех, что регулярно всплывают на coding interviews. И большинство кандидатов сначала решают её неправильно.
Типичная ошибка — проверять только родителя:
if node.left and node.left.val >= node.val:
return False
Проблема в том, что в BST ограничения наследуются от всех предков, а не только от текущего узла.
Например, вот это дерево невалидно:
10
/ \
5 15
/ \
6 20
Потому что 6 находится справа от 10, а значит должно быть больше 10, даже если 6 < 15.
Самый сильный и interview-friendly подход — min/max bounds pattern.
Идея простая:
- root начинается с диапазона (-∞, +∞)
- при движении влево текущий node становится верхней границей
- при движении вправо — нижней границей
- каждый узел должен удовлетворять:
min < node.val < max
Python-решение:
def is_valid_bst(root):
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (
validate(node.left, min_val, node.val)
and validate(node.right, node.val, max_val)
)
return validate(root, float("-inf"), float("inf"))
Почему этот подход любят на интервью:
- показывает понимание BST invariant
- O(n) по времени
- O(h) по памяти (stack depth)
- легко объяснить вслух интервьюеру
Частые edge cases, про которые забывают:
• пустое дерево → True
• один node → True
• duplicate values → обычно invalid BST
• extreme integer values → в Java/C# лучше использовать Long, а не Integer
Какую binary tree задачу вам чаще всего давали на интервью?
📍 Навигация: Вакансии • Задачи • Собесы
Библиотека питониста
#буст