Tree Node Count

Return the number of nodes in a binary tree. The empty tree has 0 nodes.

treeNodeCount(root)

The node type is:

TreeNode:
    value
    left    // reference to the left child, or nothing
    right   // reference to the right child, or nothing

Input format: level-order values with x for a missing child (an empty line is the empty tree). For example 3 9 20 x x 15 7.

Examples

3 9 20 x x 15 7   // → 5
1                  // → 1
(empty)            // → 0

Walkthrough

Thinking it through

A binary tree isn't a flat sequence — no index to loop over. But it has a self-similar shape: every node is the root of a smaller tree (left), another smaller tree (right), plus itself. That self-similarity is the key to this problem, and to almost every tree problem you'll meet.

Framing it as a recursive question

Instead of "how do I count all the nodes?", ask a smaller question: if you already knew the count for the left subtree and the right subtree, could you answer for yourself? Yes — trivially. The count for the tree rooted here is 1 (for this node) plus the left subtree's count plus the right subtree's count.

That's the core move in recursive tree thinking: figure out what a node needs from its children to compute its own answer, then trust the same logic applies recursively. You only reason about one node and what its two children hand back.

The base case

Every recursion needs a place to stop. Here it's the empty tree — a missing child. No node, no work, return 0. This handles leaves for free too: a leaf's children are both empty, so its count comes out to 1 + 0 + 0 = 1, correct without any special-casing.

Why this beats trying to do it iteratively with indices

There's no natural index into a tree the way there is into an array, so a loop-based version would need its own explicit stack or queue to track what's left to visit. Recursion gives you that stack for free — the call stack remembers, for every ancestor waiting on a subtree's answer, exactly where to resume. Sum, height, search, and path problems on trees almost always start from this same shape.

Cost

Every node is visited once, so total work is proportional to the number of nodes, and the only extra memory is the call stack, bounded by the tree's height.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.