Максимальная ширина дерева

Необходимо найти максимальную ширину бинарного дерева, то есть максимальное расстояние между вершинами на одном уровне.

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

Гарантируется, что ответ является числом меньше 2³¹ - 1, то есть влезает в тип int32 и с большим запасом влезает в тип number.

Пример

Допустим, у нас есть такое дерево:

            3               width = 1
       /         \
     5             2        width = 2
   /             /   
  1             8           width = 3
   \           /        
    3         6             width = 4
             / \
            7   4           width = 2

Визуально заполним дерево недостающими вершинами, чтобы заполнились все ряды. Ответом к задаче будет число 4, т.к. в четвертом ряду между вершиной 3 и 6 расстояние 4 (включая обе крайние вершины).

            3               width = 1
       /         \
     5             2        width = 2
   /   \         /   \
  1     ×       8     ×     width = 3
 / \   / \     / \   / \
×   3 ×   ×   6   × ×   ×   width = 4
             / \
            7   4           width = 2

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

console.log(widthOfBinaryTree(root)); // 4

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