breadth of a binary tree

You could use a recursive function that returns two values for a given node: the extent of the subtree at that node towards the left (a negative number or zero), and the extent to the right (zero or positive). So for the example tree given in the question it would return -1, and 3.

To find these extends is easy when you know the extents of the left child and of the right child. And that is where the recursion kicks in, which in fact represents a depth-first traversal.

Here is how that function would look in 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)

The breadth is simply the difference between the two extents returned by the above function, plus 1 (to count for the root node):

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

The complete Python code with the example tree, having 6 nodes, as input:

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