Размер Complete Tree

Дано complete tree. Определить, сколько в нем вершин.

Определения

Perfect Tree — бинарное дерево, в котором целиком заполнены все уровни.

     1
   /   \
  5     2
 / \   / \
7   3 6   9

Complete Tree — бинарное дерево, в котором целиком заполнены все уровни, кроме последнего. Последний уровень может быть заполнен целиком или нет, но если он заполнен частично, то заполнены вершины слева направо без пропусков.

Из perfect tree выше могут получиться такие complete tree:

     1             1           1           1
   /   \         /   \       /   \       /   \
  5     2       5     2     5     2     5     2
 / \   / \     / \   /     / \         /  
7   3 6   9   7   3 6     7   3       7

Больше определений см. в Wikipedia.

Пример

const root = {
  value: 1,
  left: {
    value: 5,
    left: {
      value: 7,
      left: null,
      right: null,
    },
    right: {
      value: 3,
      left: null,
      right: null,
    },
  },
  rigth: {
    value: 2,
    left: null,
    right: null,
  },
};

console.log(countNodes(root)); // 5

ЗадачаРедактор