Обходы дерева: DFS и BFS

Дерево обходят либо «вглубь» (DFS), либо «по уровням» (BFS) — выбор зависит от задачи.

Бинарное дерево — структура, где каждый узел имеет до двух потомков (левого и правого); обход — порядок посещения всех узлов.

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

      4
     / \
    2   6
   / \
  1   3

DFS: обход в глубину

Идём как можно глубже по одной ветке, потом возвращаемся. Три порядка: in-order (лево, корень, право), pre-order (корень, лево, право), post-order (лево, право, корень). Для дерева поиска именно in-order даёт элементы по возрастанию.

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

def inorder(node, out):
    if not node:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

result = []
inorder(root, result)
print(result)

Вывод:

[1, 2, 3, 4, 6]

BFS: обход по уровням

Посещаем узлы уровень за уровнем: сначала корень, потом его детей, потом внуков. Используем очередь: достаём узел, кладём его детей в конец.

from collections import deque

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

def bfs_levels(root):
    if not root:
        return []
    levels = []
    q = deque([root])
    while q:
        size = len(q)
        level = []
        for _ in range(size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(bfs_levels(root))

Вывод:

[[4], [2, 6], [1, 3]]

Как работает под капотом

DFS естественно реализуется рекурсией: стек вызовов сам «помнит», куда вернуться. Глубина рекурсии — высота дерева, то есть память O(h); для несбалансированного дерева это O(n). BFS использует явную очередь: запоминая size = len(q) в начале цикла, мы отделяем один уровень от другого. Оба обхода посещают каждый узел один раз — O(n) время.

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

• Путать порядки DFS: для отсортированного вывода BST нужен именно in-order.
• В BFS не фиксировать size уровня — тогда уровни «слипнутся».
• Использовать DFS на глубоком дереве и упереться в лимит рекурсии (тогда пишут итеративно через стек).

Итог

• DFS (рекурсия) — вглубь; in/pre/post-order различаются позицией корня.
• BFS (очередь) — по уровням; фиксируйте размер уровня.
• Оба обхода O(n) по времени; память DFS — O(высоты), BFS — O(ширины).