😱 Как правильно валидировать BST на Python (и не завалить интервью) — 31 мая 2026 г. в 17:15:33.658
😱 Как правильно валидировать BST на Python (и не завалить интервью) Задача 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