Валидация бинарного дерева поиска

Валидация бинарного дерева поиска (BST)

Понимание задачи

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

Частая ошибка: Проверять только соседей узла, но нужно проверять ALL значения в левом и правом поддеревьях!

Структура узла дерева

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Решение 1: С отслеживанием границ O(n)

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

def is_valid_bst(root: TreeNode) -> bool:
    """
    Проверяет, является ли дерево валидным BST.
    
    Используем границы: для левого поддерева max = текущее значение,
    для правого min = текущее значение.
    
    Args:
        root: Корень дерева
    
    Returns:
        True если валидное BST, иначе False
    """
    def validate(node: TreeNode, min_val: float, max_val: float) -> bool:
        # Базовый случай
        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'))

Пример пошагово для валидного дерева:

        2
       / \
      1   3

Шаг 1: validate(2, -inf, +inf)
  2 в (-inf, +inf)? Да ✓
  Левое: validate(1, -inf, 2)
    1 в (-inf, 2)? Да ✓
    Листьевого левого/правого нет
  Правое: validate(3, 2, +inf)
    3 в (2, +inf)? Да ✓
    Листьевого левого/правого нет
  
Результат: True ✓

Пример с ошибкой:

        5
       / \
      1   4
         / \
        3   6

Шаг 1: validate(5, -inf, +inf)
  5 в (-inf, +inf)? Да ✓
  Левое: validate(1, -inf, 5)
    1 в (-inf, 5)? Да ✓
  Правое: validate(4, 5, +inf)
    4 в (5, +inf)? НЕТ! ✗
    4 должен быть > 5, но 4 < 5

Результат: False ✓

Сложность:

• Время: O(n) - посещаем каждый узел один раз
• Память: O(h) - высота дерева (рекурсивный стек)

Решение 2: In-Order обход (интересный способ)

В валидном BST in-order обход даёт отсортированный массив!

def is_valid_bst_inorder(root: TreeNode) -> bool:
    """Использует свойство in-order обхода BST."""
    def inorder(node):
        if not node:
            return True
        
        # Проверяем левое поддерево
        if not inorder(node.left):
            return False
        
        # Проверяем текущий узел
        # Должен быть больше предыдущего
        if node.val <= inorder.prev:
            return False
        inorder.prev = node.val
        
        # Проверяем правое поддерево
        return inorder(node.right)
    
    inorder.prev = float('-inf')
    return inorder(root)

Решение 3: Итеративный обход (без рекурсии)

def is_valid_bst_iterative(root: TreeNode) -> bool:
    """Итеративный способ с явным стеком."""
    stack = [(root, float('-inf'), float('inf'))]
    
    while stack:
        node, min_val, max_val = stack.pop()
        
        if not node:
            continue
        
        # Проверяем границы
        if node.val <= min_val or node.val >= max_val:
            return False
        
        # Добавляем поддеревья в стек
        stack.append((node.left, min_val, node.val))
        stack.append((node.right, node.val, max_val))
    
    return True

Тесты

def test_is_valid_bst():
    # Валидный BST
    #     2
    #    / \
    #   1   3
    node1 = TreeNode(2)
    node1.left = TreeNode(1)
    node1.right = TreeNode(3)
    
    assert is_valid_bst(node1) == True
    
    # Невалидный: нарушение справа внизу
    #     5
    #    / \
    #   1   4
    #      / \
    #     3   6
    node2 = TreeNode(5)
    node2.left = TreeNode(1)
    node2.right = TreeNode(4)
    node2.right.left = TreeNode(3)
    node2.right.right = TreeNode(6)
    
    assert is_valid_bst(node2) == False
    
    # Граничный: только соседи в порядке
    #     3
    #    / \
    #   1   5
    #      /
    #     4
    node3 = TreeNode(3)
    node3.left = TreeNode(1)
    node3.right = TreeNode(5)
    node3.right.left = TreeNode(4)
    
    assert is_valid_bst(node3) == True
    
    # Один узел
    node4 = TreeNode(42)
    assert is_valid_bst(node4) == True
    
    # Пустое дерево
    assert is_valid_bst(None) == True
    
    print("Все тесты пройдены!")

test_is_valid_bst()

Частые ошибки

# ОШИБКА 1: Проверяем только соседей
def is_valid_bst_WRONG(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:  # Только сосед!
        return False
    if node.right and node.right.val <= node.val:  # Только сосед!
        return False
    return is_valid_bst_WRONG(node.left) and is_valid_bst_WRONG(node.right)

# Эта функция вернёт True для невалидного дерева:
#       5
#      / \
#     1   4
#        / \
#       3   6
# Потому что 4 > 5 проверяется только для прямого потомка,
# но 4 находится в правом поддереве 5 и должен быть > 5!

# ПРАВИЛЬНО: Использовать границы
def is_valid_bst_CORRECT(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    if node.val <= min_val or node.val >= max_val:
        return False
    return (is_valid_bst_CORRECT(node.left, min_val, node.val) and
            is_valid_bst_CORRECT(node.right, node.val, max_val))

Сравнение подходов

Ключевые моменты для интервью

1. Главная ошибка: Проверять только соседей, забыть о границах
2. Решение: Отслеживать min/max для каждого узла
3. Оптимальность: O(n) время, нельзя быстрее (нужно посетить все узлы)
4. Граничные случаи: Пустое дерево, один узел, очень глубокое дерево
5. Бонус: Объяснить in-order обход и его свойства