The structure of a tree node

In code, each node is a small record with three fields: the value it stores, a link to the left child, and a link to the right child.

If a child does not exist, that link holds nothing at all: null in most languages, None in Python. Every tree problem starts by asking what is in this node, and what do the two links lead to.

The value field: is what this node stores.

The left and right links: lead to the child nodes, or to nothing.

root = [1, 2, 3, 4, 5]

count(1) doesn't count everything itself. It trusts its two subtrees to report their own counts.

Move 1 of 6

Counting by trusting subtrees

Think of a manager asking how many people work under them. They do not count everyone themselves. They ask each of their two team leads, who ask theirs, and each reports back a number.

The manager adds the two reports and 1 for themself. The very first thing to check is whether there is anyone there at all: an empty spot counts as 0.

One plus left plus right: combines this node with both subtrees.

Check for nothing first: asking an empty spot for its children crashes.

In code

if not root:
    return 0
left = count_nodes(root.left)
right = count_nodes(root.right)
return 1 + left + right