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

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

Три классических обхода DFS (поиск в глубину) отличаются только одним: когда обрабатывается текущий узел — до потомков, между потомками или после потомков. Именно отсюда и возникают их названия. Начнём с самого полезного. In-order обходит узлы в порядке Left → Node → Right. Для каждого узла: сначала идём в левое поддерево, потом обрабатываем сам узел, потом идём в правое поддерево.

static void InOrder(TreeNode? node)
{
    if (node == null) return;
    InOrder(node.Left);              // сначала левое поддерево
    Console.Write(node.Val + " ");   // потом сам узел
    InOrder(node.Right);             // потом правое поддерево
}

// Для BST: 8, 3, 10, 1, 6, 14, 4, 7, 13
// In-order выводит: 1 3 4 6 7 8 10 13 14

Для BST этот код выведет все элементы в отсортированном порядке. Никакой сортировки — просто обход. Почему? Свойство BST: левый потомок всегда меньше родителя, правый — всегда больше. In-order проходит узлы именно в этом естественном порядке — от меньшего к большему.

Порядок: 1 → 3 → 6 → 8 → 10 → 14. Именно так — от меньшего к большему. Никакой сортировки — только обход. Меняем порядок трёх действий — получаем другие обходы. Pre-order: Node → Left → Right. Узел обрабатывается до потомков — отсюда «pre» (до).

static void PreOrder(TreeNode? node)
{
    if (node == null) return;
    Console.Write(node.Val + " "); // сначала сам узел
    PreOrder(node.Left);
    PreOrder(node.Right);
}
// Для BST (8, 3, 10, 1, 6, 14): 8 3 1 6 10 14

Pre-order всегда начинается с корня. Это идеальный порядок для копирования дерева: если вставлять узлы в новый BST в порядке pre-order, получится точная копия исходного дерева. По той же причине pre-order используют для сериализации — сохранения дерева в файл или отправки по сети. Получатель строит дерево, вставляя элементы в том же порядке.

Post-order: Left → Right → Node. Узел обрабатывается после обоих потомков — отсюда «post» (после).

static void PostOrder(TreeNode? node)
{
    if (node == null) return;
    PostOrder(node.Left);
    PostOrder(node.Right);
    Console.Write(node.Val + " "); // узел в конце
}
// Для BST (8, 3, 10, 1, 6, 14): 1 6 3 14 10 8

Корень — всегда последний. Post-order незаменим, когда потомков нужно обработать до родителя:

• Удаление дерева: нельзя удалить узел, пока у него есть дети — сначала удаляем листья, потом их родителей, и так до корня.
• Вычисление размера поддеревьев: размер узла = 1 + размер левого поддерева + размер правого поддерева — нужно знать размеры детей раньше родителя.
• Вычисление высоты: функция Height из прошлого урока — это и есть post-order обход по сути.

Все три обхода выше — DFS (поиск в глубину): мы ныряем как можно глубже, потом возвращаемся. Но есть и другой подход — обходить дерево по уровням, слева направо. Это level-order, он же BFS (поиск в ширину).

Для BFS нужна очередь. Кладём корень в очередь. На каждом шаге: достаём узел, обрабатываем его, добавляем его потомков в очередь. Почему очередь? Потому что она обеспечивает FIFO — обрабатываем в том порядке, в каком добавили. Корень → его дети → их дети — строго по уровням.

static void LevelOrder(TreeNode? root)
{
    if (root == null) return;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        Console.Write(node.Val + " ");

        if (node.Left  != null) queue.Enqueue(node.Left);
        if (node.Right != null) queue.Enqueue(node.Right);
    }
}
// Для BST (8, 3, 10, 1, 6, 14): 8 3 10 1 6 14

Level-order выдаёт узлы ровно в том порядке, в каком мы бы прочитали дерево сверху вниз. Это полезно, когда нужно обработать дерево по уровням: найти ширину каждого уровня, проверить сбалансированность, красиво напечатать дерево. В отличие от DFS-обходов, BFS использует явную структуру данных — очередь, а не стек вызовов рекурсии.

Итого — четыре способа обойти дерево:

Стоит понять, что происходит внутри рекурсии при обходе. Когда вы вызываете InOrder(root), стек вызовов разворачивается так:

// InOrder(8) — входим
//   InOrder(3) — входим
//     InOrder(1) — входим
//       InOrder(null) — выходим
//       print(1)
//       InOrder(null) — выходим
//     InOrder(6) — входим
//       InOrder(null) — выходим
//       print(6)
//       InOrder(null) — выходим
//     print(3)
//   print(8)
//   InOrder(10) — входим
//     ...
// Итого вызовов: 2n+1 (каждый узел + каждый null-потомок)

Глубина стека равна высоте дерева — O(h). Для сбалансированного дерева это O(log n), что очень мало. Для миллиона элементов — около 20 уровней вложенности. Если дерево вырожденное (цепочка), глубина стека = n — для большого n это может привести к StackOverflowException. В таких случаях рекурсию заменяют итеративным вариантом с явным стеком.

Итеративный in-order с явным стеком:

static void InOrderIterative(TreeNode? root)
{
    var stack = new Stack<TreeNode>();
    var current = root;

    while (current != null || stack.Count > 0)
    {
        // Идём налево до упора
        while (current != null)
        {
            stack.Push(current);
            current = current.Left;
        }

        // Обрабатываем узел
        current = stack.Pop();
        Console.Write(current.Val + " ");

        // Переходим вправо
        current = current.Right;
    }
}

Логика та же: сначала спускаемся влево до упора, потом обрабатываем и уходим вправо. Просто вместо стека вызовов — явный Stack<T>. Сложность та же — O(n) по времени, O(h) по памяти.

Отдельный интересный момент: pre-order обход удобно реализуется итеративно через стек, причём порядок добавления потомков — обратный (сначала правый, потом левый), чтобы левый оказался на вершине и обрабатывался первым:

static void PreOrderIterative(TreeNode? root)
{
    if (root == null) return;
    var stack = new Stack<TreeNode>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var node = stack.Pop();
        Console.Write(node.Val + " ");

        if (node.Right != null) stack.Push(node.Right); // правый — в стек первым
        if (node.Left  != null) stack.Push(node.Left);  // левый — поверх, выйдет первым
    }
}

Для level-order мы уже видели очередь. Её особое применение — нахождение максимальной ширины дерева: сколько узлов на самом широком уровне. Для этого в цикле обработки очереди нужно знать, сколько узлов на текущем уровне, и считать их отдельно:

static int MaxWidth(TreeNode? root)
{
    if (root == null) return 0;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int maxWidth = 0;

    while (queue.Count > 0)
    {
        int levelSize = queue.Count; // Сколько узлов на текущем уровне
        maxWidth = Math.Max(maxWidth, levelSize);

        for (int i = 0; i < levelSize; i++)
        {
            var node = queue.Dequeue();
            if (node.Left  != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
    }
    return maxWidth;
}

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

На собеседованиях обходы деревьев — обязательная тема. Классическая задача: «сериализовать и десериализовать бинарное дерево» (pre-order с маркерами null для пустых потомков). Другая: «проверить, является ли дерево зеркальным» (два рекурсивных обхода одновременно — левый и правый). Если вы уверенно пишете все четыре обхода — 80% задач на деревья вам по плечу.

In-order (симметричный обход) — Left → Node → Right. Для BST выдаёт элементы в отсортированном порядке за O(n). Фактически бесплатная сортировка.

Pre-order (прямой обход) — Node → Left → Right. Узел обрабатывается первым. Используется для копирования и сериализации дерева.

Post-order (обратный обход) — Left → Right → Node. Узел обрабатывается последним. Используется для удаления дерева, вычисления размеров поддеревьев, вычисления выражений в AST.

Level-order (обход по уровням) — BFS с очередью Queue<T>. Узлы обходятся слева направо, уровень за уровнем.

DFS vs BFS: in-order, pre-order, post-order используют стек (рекурсию) — поиск в глубину. Level-order использует очередь — поиск в ширину.

Запоминалка: название = когда обрабатывается узел. Pre — до потомков. In — между ними. Post — после. Порядок детей всегда одинаков: сначала левый, потом правый.