Алгоритмы обхода двоичного дерева

Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин (их называют левым и правым ребенком).

Пример двоичного дерева:

Class BinaryTree:

    class BinaryTree {
      public int value;
      public BinaryTree left;
      public BinaryTree right;

      public BinaryTree(int value) {
        this.value = value;
      }
    }

Чтобы обойти вершины двоичного дерева можно использовать алгоритм поиска в глубину (DFS). Обычно в алгоритмических задачах на двоичные деревья используется рекурсивная версия этого алгоритма. Для деревьев этот алгоритм сильно упрощается, т.к. нам не надо использовать visited. Для деревьев нам не нужно помечать вершины посещенными, потому что в дереве нет циклов по определению. А также мы будем идти от родительских вершин к дочерним.

Поэтому для двоичного дерева алгоритм упрощается до:

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      visit(tree);
      dfs(tree.left);
      dfs(tree.right);
    }

Такой алгоритм обхода двоичного дерева называется pre-order traversal: Tree Traversal.

Мы вначале посещаем вершину, а потом вызываем рекурсивно для левого и правого ребенка. Это позволяет посещать вершины в топологическом порядке. Вначале родителей, потом детей.

Есть еще вариации обхода двоичного дерева, которые называются соответственно in-order (вначале посещаем левого ребенка, потом вершину, потом правого ребенка):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      visit(tree);
      dfs(tree.right);
    }

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

И post-order (вначале посещаем левого и правого ребенка, а потом уже саму вершину):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      dfs(tree.right);
      visit(tree);
    }

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

Обычно, надо написать какую-то кастомную логику под задачу для каждой посещенной вершины вместо метода visit. Иногда надо добавить дополнительные if-else для рекурсивных вызовов. Иногда надо передавать или возвращать какие-то значения или объекты из метода dfs.