Gathering the answer from the children

Most tree questions are solved bottom-up: each node asks its children, combines the two answers it gets and hands its own answer up. For depth the combining is "take the larger and add one"; for the number of nodes it is "add the two and add one".

1def depth(node):
2    if node is None:
3        return 0
4    return 1 + max(depth(node.left), depth(node.right))

The depth of an empty tree is 0, and of a one-node tree 1. The number you return in the base case shifts every answer: return 1 instead of 0 and every tree comes out one too deep.

Sometimes you ask a question about the node itself: is this a leaf? A leaf is a node whose children are both None. Counting leaves there are three cases: an empty tree (0), a leaf (1), an inner node (the two subtrees added; itself not counted).

Tasks