Рекурсивный проход по бинарному дереву с подсчётом суммы значений

Условие

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

const binaryTree = {
  value: 6,
  left: {
    value: 5,
    left: {
      value: 3,
      left: {
        value: 1
      }
    },
    right: {
      value: 7
    }
  },
  right: {
    value: 10,
    left: {
      value: 4
    },
    right: {
      value: 5
    }
  }
}

Ответ

Сумма дерева равна значению текущего узла плюс суммы левого и правого поддеревьев. Отсутствующий узел даёт 0; для приведённого дерева результат равен 41.

function sumTree(node) {
  if (node == null) return 0;
  return node.value + sumTree(node.left) + sumTree(node.right);
}

Каждый узел посещается один раз: время O(n), стек O(h), где h — высота дерева. Решение предполагает настоящее дерево без циклов и числовые значения. Для очень глубокой цепочки рекурсию заменяют явным стеком, чтобы не переполнить стек вызовов.