DSA Factory
Free lessonsTrees · Stage 0 · Nodes and depth · Step 1

Count the nodes

Answer 0 for an empty tree, and 1 plus left and right counts for every node. About 8 minutes.

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]
42513

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
Quick check

If a tree has a root whose left child has 2 nodes and whose right child is null, what is the total count?

  1. A3 nodes
  2. B2 nodes
  3. C4 nodes
Show the answer

3 nodes. 1 (the root) + 2 (left subtree) + 0 (right subtree) = 3.

Your problem

Count the nodes

Given the root of a binary tree, return the total number of nodes in the tree. If the tree is empty (root is null), return 0.

Example
root = [1, 2, 3] → 3

0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding