Бинарное дерево: как устроено и какие задачи дают на собеседованиях

Структуры данных — одна из тем, которые на собеседованиях всплывают с пугающей регулярностью. Среди всех этих структур бинарное дерево занимает особое место. Не потому, что оно сложное. А потому, что вопросы про него любят задавать почти все — от стартапов до гигантов вроде Google и Microsoft.

Разбирать бинарное дерево стоит не как абстрактный конструкт из университетского курса. Эта структура имеет сугубо прикладное значение и лежит в основе множества реальных механизмов: от баз данных до файловых систем и компиляторов. Если вы когда-нибудь писали код, который искал что-то в отсортированном массиве, вы уже пользовались логикой, родственной бинарному дереву поиска. 

Разбираться будем последовательно. Сначала выясним, что это вообще такое и чем одно бинарное дерево отличается от другого. Потом — как с ним работать, какие операции бывают и почему они иногда тормозят. Отдельно пройдёмся по обходам: это классика, которую спрашивают на каждом втором собеседовании. В финале разберём реальные задачи с кодом.

Что такое бинарное дерево

Бинарное дерево — это структура данных, в которой каждый узел может иметь не более двух потомков. Их обычно называют левым и правым. 

Звучит просто. Но именно эта простота и делает бинарное дерево такой полезной штукой.

Представьте себе генеалогическое древо, где у каждого человека может быть максимум двое детей. Только в программировании мы храним не людей, а данные: числа, строки, какие угодно объекты. И связи идут не от родителей к детям, а от корня к листьям.

Корень — это самый верхний узел, с которого всё начинается.  Листья — узлы, у которых нет потомков.  Всё, что между ними, называется внутренними узлами. Любой узел со всеми своими потомками образует поддерево.

Важно уточнение: узел может иметь одного потомка. Или не иметь ни одного. Главное — не больше двух. Это и есть определяющее свойство бинарного дерева. 

Ещё один момент, который часто упускают из виду: бинарное дерево может быть пустым. В некоторых определениях пустое дерево тоже считается бинарным деревом. Во многих алгоритмах пустое дерево служит базовым случаем рекурсии.

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

У каждого узла есть значение и ссылки на левого и правого потомка.  В языках со статической типизацией это обычно выглядит как структура с тремя полями: данные, левый указатель, правый указатель. В динамических языках — как объект или словарь с теми же полями.

Вот как это выглядит на Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Метод __init__ — это конструктор класса: он вызывается при создании нового узла и записывает его значение и ссылки на потомков.

Бинарное дерево поиска — чем отличается от обычного бинарного дерева

Бинарное дерево и бинарное дерево поиска — не одно и то же.

Бинарное дерево поиска (BST, Binary Search Tree) — это бинарное дерево с дополнительным правилом: для любого узла все значения в левом поддереве меньше значения этого узла, а все значения в правом поддереве — больше. 

Это правило превращает обычную структуру в мощный инструмент для поиска. 

Причина эффективности в том, что благодаря упорядоченности поиск превращается в последовательность сравнений: зашли в узел — сравнили искомое значение с текущим — если меньше, идём налево, если больше — направо. На каждом шаге мы отбрасываем примерно половину дерева.

Приведём пример. Есть дерево с корнем 10. Левый потомок — 5, правый — 15. У 5 левый потомок — 3, правый — 7. У 15 левый — 12, правый — 18.

Это бинарное дерево поиска: 3 < 5 < 7 < 10 < 12 < 15 < 18. Всё работает.

А теперь представим дерево с корнем 10, левым потомком 15 и правым потомком 5. Это бинарное дерево (у каждого узла не более двух потомков), но не BST, потому что правило нарушено: в левом поддереве (15) оказалось значение больше корня.

На собеседованиях эту разницу проверяют часто. Могут дать дерево и спросить: «Это BST?» И если вы не обратите внимание на порядок, ответите неверно.

Какие операции есть у дерева поиска и какая у них сложность

У бинарного дерева поиска три основные операции: поиск, вставка и удаление. 

Поиск начинается с корня. Сравниваем искомое значение со значением в текущем узле. Если равны — нашли. Если меньше — идём в левое поддерево. Если больше — в правое. Повторяем, пока не найдём или не упрёмся в пустой узел. 

Вставка работает похоже. Ищем место для нового узла так же, как при поиске. Когда доходим до пустого места — вставляем новый узел.

Удаление — самая интересная операция. Тут три случая в зависимости от того, сколько потомков у удаляемого узла:

Теперь о сложности.

Операция	Средний случай	Худший случай
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

В среднем случае операции занимают O(log n) — логарифмическое время. Это быстро. Но только если дерево сбалансировано.

В худшем случае — O(n). Это уже линейное время, как в обычном списке. 

Почему дерево может «вырождаться» и как это может пригодиться на собеседовании

Вырожденное дерево — это когда каждый узел имеет только одного потомка. По сути, это связный список, замаскированный под дерево. 

Так дерево вырождается, когда элементы вставляются в BST в отсортированном порядке. Например, при вставке последовательности 1, 2, 3, 4, 5 каждый новый элемент оказывается больше предыдущего и уходит в правое поддерево. В итоге каждый узел имеет только правого потомка. 

Высота такого дерева равна количеству узлов.  Поиск в нём превращается в последовательный перебор — O(n). Все преимущества BST теряются.

Обходы дерева — преобразуем структуру в последовательность

Дерево — структура нелинейная. Чтобы работать с ним, иногда нужно превратить его в линейную последовательность. Для этого существуют обходы.

Есть три классических способа обхода бинарного дерева: префиксный (preorder), инфиксный (inorder) и постфиксный (postorder). 

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

Префиксный обход: посещаем узел, потом левое поддерево, потом правое. 

Порядок: корень → левое поддерево → правое поддерево.

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)

Инфиксный обход: левое поддерево, потом узел, потом правое поддерево. 

Порядок: левое поддерево → корень → правое поддерево.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

Постфиксный обход: левое поддерево, потом правое, потом узел. 

Порядок: левое поддерево → правое поддерево → корень.

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

Инфиксный обход — почему он даёт сортированную последовательность именно для BST

Это свойство — одна из главных причин, почему BST вообще имеет смысл. 

Если выполнить инфиксный обход бинарного дерева поиска, мы получим значения в порядке возрастания. 

Почему? Потому что правило BST гарантирует: все значения в левом поддереве меньше корня, все значения в правом — больше. Инфиксный обход идёт слева направо: сначала все меньшие, потом корень, потом все большие. Рекурсивно применяя это правило к каждому поддереву, получаем полную сортировку.

Это свойство используют, когда нужно получить отсортированные данные из дерева без дополнительной сортировки в Python. Просто запустили инфиксный обход — и готово.

Обход в ширину — когда нужен не только порядок «сверху-вниз»

Три предыдущих обхода — это варианты поиска в глубину, или DFS. Мы уходим вглубь дерева, насколько возможно, прежде чем переходить к соседним узлам.

Но есть и другой подход — поиск в ширину (BFS, Breadth-First Search), он же обход по уровням. 

При обходе по уровням мы посещаем все узлы на одном уровне, потом переходим на следующий. 

Для этого используется очередь collections.deque, из начала которой можно быстро извлекать узлы методом popleft().

from collections import deque

def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

На собеседованиях эту задачу дают в двух вариантах: вывести значения по уровням или вернуть список списков в Python, где каждый внутренний список содержит отдельный уровень дерева.

Обход в ширину полезен, когда нужно найти что-то на определённой глубине или когда структура дерева такова, что глубокое погружение неэффективно.

Реальные задачи с собеседований — разбор с кодом

Теперь перейдём к самому интересному — задачам, которые реально дают на технических интервью. 

Инвертировать бинарное дерево

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

Эта задача стала мемом после истории с создателем Homebrew Максом Хауэллом. В 2015 году он проходил собеседование в Google и не смог решить на доске задачу по инверсии бинарного дерева. 

После интервью Хауэлл написал в соцсети: «Google: 90% наших инженеров используют написанное вами ПО (Homebrew), но вы не можете инвертировать бинарное дерево на белой доске, так что идите вы…». Позже задача «Invert Binary Tree» появилась на LeetCode под номером 226 с пометкой, что она вдохновлена тем самым твитом Макса Хауэлла.

С тех пор эту задачу действительно часто спрашивают на собеседованиях.

Идея решения: рекурсивно обойти дерево и для каждого узла поменять местами left и right.

Сложность: O(n) по времени и O(h) по памяти под стек вызовов, где h — высота дерева.

def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

В конце функция использует return, чтобы вернуть изменённый корень дерева. Мы меняем местами поддеревья, а не значения.

Проверить, является ли дерево валидным BST

Условие: дано бинарное дерево. Определить, является ли оно бинарным деревом поиска. 

Идея решения: при инфиксном обходе BST мы должны получать строго возрастающую последовательность. Можно выполнить обход и проверять, что каждый следующий элемент больше предыдущего.

Но есть более элегантный способ — рекурсивная проверка с передачей допустимого диапазона значений для каждого узла.

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    if root is None:
        return True
    if not (min_val < root.value < max_val):
        return False
    return (is_valid_bst(root.left, min_val, root.value) and
            is_valid_bst(root.right, root.value, max_val))

Сложность: O(n) по времени, O(h) по памяти.

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

Найти наименьшего общего предка двух узлов (LCA)

Условие: дано бинарное дерево (не обязательно BST) и два узла. Найти их наименьшего общего предка — самый глубокий узел, который является предком обоих. 

Идея решения: рекурсивно спускаемся от корня. Если текущий узел совпадает с одним из искомых — возвращаем его. Ищем в левом и правом поддеревьях. Если оба поддерева вернули не None — значит, текущий узел и есть LCA. Если только одно — возвращаем его.

def lowest_common_ancestor(root, p, q):
    if root is None or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Сложность: O(n) по времени, O(h) по памяти.

Для BST есть более быстрое решение: идём от корня и смотрим на значения. Если оба искомых узла меньше текущего — идём налево. Если оба больше — направо. Иначе текущий узел и есть LCA. Сложность O(h).

Проверить, симметрично ли дерево

Условие: дано бинарное дерево. Проверить, является ли оно зеркально симметричным относительно корня. 

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

def is_symmetric(root):
    if root is None:
        return True
    return is_mirror(root.left, root.right)

def is_mirror(left, right):
    if left is None and right is None:
        return True
    if left is None or right is None:
        return False
    return (left.value == right.value and
            is_mirror(left.left, right.right) and
            is_mirror(left.right, right.left))

Сложность: O(n) по времени, O(h) по памяти.

Частые вопросы

Чем бинарное дерево отличается от бинарного дерева поиска?

Бинарное дерево — это структура, где у каждого узла не более двух потомков. Бинарное дерево поиска — это бинарное дерево с дополнительным правилом упорядоченности: все значения в левом поддереве меньше значения узла, все значения в правом — больше. 

Что такое сбалансированное дерево и зачем оно нужно?

Сбалансированное дерево — это дерево, в котором высоты левого и правого поддеревьев каждого узла отличаются не более чем на 1.  Баланс нужен, чтобы операции поиска, вставки и удаления работали за O(log n), а не вырождались в O(n). 

Какая сложность поиска в худшем случае?

В худшем случае, когда дерево вырожденное (каждый узел имеет только одного потомка), поиск работает за O(n).  Это происходит, если элементы вставляются в BST в отсортированном порядке. 

Почему инфиксный обход BST даёт отсортированный список?

Потому что правило BST гарантирует: все элементы в левом поддереве меньше корня, все в правом — больше.  Инфиксный обход посещает левое поддерево, потом корень, потом правое — именно в таком порядке и получается сортировка.

Что такое обход в ширину и когда он применяется?

Обход в ширину (BFS, level-order traversal) посещает узлы уровень за уровнем, слева направо.  Применяется, когда нужно найти что-то на определённой глубине, или когда структура дерева делает глубокий обход неэффективным. 

Бинарные деревья — тема, которая не теряет актуальности. На собеседованиях задачи по этим структурам дают не из любви к классике: они отлично проверяют понимание рекурсии, работы с указателями и оценки сложности алгоритмов. Если вы разобрались с тем, что здесь написано, и решили хотя бы пару задач самостоятельно — вы уже в хорошей позиции. 

Для тех, кто хочет потренироваться дальше, есть платформы вроде LeetCode — там собраны сотни задач на деревья. Можно отфильтровать по сложности и проходить одну за другой. Главное — не пытаться запомнить решения, а понять паттерны. Как только вы увидите, что за разными задачами стоят одни и те же приёмы — обход, рекурсия, передача диапазона, — деревья перестанут быть страшными.

Советуем дополнительно почитать