Обход дерева

O(n)

Рекурсивно (или с явной очередью/стеком) посетить каждый узел дерева в заданном порядке, собирая или объединяя значения по пути.

Сигналы

бинарное дерево задано как корневой узел с указателями left/rightпосетить каждый узел (прямой / симметричный / обратный / по уровням)посчитать глубину, высоту или сумму по всему деревуобработать детей до или после родителявывод по уровням (BFS с очередью)

Шаблон

function traverse(node, result = []) {
    if (!node) return result; // base case
    traverse(node.left, result);
    result.push(node.val); // inorder here; move this line for pre/post
    traverse(node.right, result);
    return result;
}

Похоже, но не то

BFS/DFS по графу: У дерева нет циклов, и у каждого узла ровно один родитель, поэтому обычный рекурсивный обход или обход через очередь никогда не заходит в узел повторно и не требует множества посещённых. У обычного графа есть циклы и несколько родителей, поэтому BFS/DFS там обязаны хранить множество посещённых узлов.

n узлов, каждый посещается ровно один раз -> O(n) времени. Глубина рекурсии O(h) (или явная очередь O(n) для обхода по уровням), причём h может доходить до n на вырожденном дереве.

Изучить этот паттерн