Подсчёт суммарного значения всех узлов бинарного дерева

Условие

Дана структура бинарного дерева, где каждый узел хранит числовое значение и может иметь левый и правый потомки. Необходимо реализовать функцию, которая рекурсивно проходит по всем узлам и возвращает сумму их значений. Пример реализации на TypeScript:

interface ITree {
  value: number;
  left?: ITree;
  right?: ITree;
}

const tree: ITree = {
  left: {
    left: {
      left: {
        right: {
          left: {
            value: 7,
          },
          right: {
            value: 14,
          },
          value: 66,
        },
        value: 23,
      },
      value: 90,
    },
    right: {
      value: 67,
    },
    value: 34,
  },
  right: {
    value: 11,
  },
  value: 16,
};

function treeValueSum(tree: ITree) {
  let sum = tree.value;

  if (tree.left) {
    sum += treeValueSum(tree.left);
  }

  if (tree.right) {
    sum += treeValueSum(tree.right);
  }

  return sum;
}

console.log(treeValueSum(tree));
console.log(treeValueSum(tree) === 328);

Ответ

Приведённая рекурсивная функция уже корректна: сумма узлов равна 328, поэтому второй console.log выведет true. Каждый узел добавляется ровно один раз.

Можно компактно записать тот же обход с поддержкой отсутствующего корня:

function treeValueSum(tree?: ITree): number {
  if (!tree) return 0;
  return tree.value + treeValueSum(tree.left) + treeValueSum(tree.right);
}

В примере складываются 16, 34, 90, 23, 66, 7, 14, 67 и 11. Время O(n), глубина стека O(h), где h — высота дерева. Очень глубокое вырожденное дерево лучше обходить явным стеком; для настоящего дерева без циклов Set посещённых узлов не нужен.