ширина бинарного дерева

Вы можете использовать рекурсивную функцию, которая возвращает два значения для данного узла: степень поддерева на этом узле влево (отрицательное число или ноль) и степень справа (ноль или положительная). Таким образом, для дерева примеров, заданного в вопросе, оно вернет -1 и 3.

Чтобы найти эти расширения, легко узнать, когда вы знаете экстенты левого дочернего элемента и правого дочернего элемента. И именно здесь начинается рекурсия, которая на самом деле представляет собой обход глубины.

Вот как эта функция будет выглядеть в Python:

def extents(tree):
    if not tree:
        # If a tree with just one node has extents 0 and 0, then "nothing" should
        #  have a negative extent to the right and a positive on the left, 
        #  representing a negative breadth
        return 1, -1
    leftleft, leftright = extents(tree.left)
    rightleft, rightright = extents(tree.right)
    return min(leftleft-1, rightleft+1), max(leftright-1, rightright+1)

Ширина просто разница между двумя экстентами, возвращаемыми вышеуказанной функцией, плюс 1 (для подсчета для корневого узла):

def breadth(tree):
    leftextent, rightextent = extents(tree)
    return rightextent-leftextent+1

Полный код Python с деревом примеров с 6 узлами в качестве входных данных:

from collections import namedtuple
Node =  namedtuple('Node', ['left', 'right'])

def extents(tree):
    if not tree:
        return 1, -1
    leftleft, leftright = extents(tree.left)
    rightleft, rightright = extents(tree.right)
    return min(leftleft-1, rightleft+1), max(leftright-1, rightright+1)

def breadth(tree):
    left, right = extents(tree)
    return right-left+1

# example tree as given in question
tree = Node(
    Node(
        None,
        Node(None, Node(None, Node(None, None)))
    ),
    Node(None, None)
)

print(breadth(tree)) # outputs 4