Binary Tree Structure and Terminology
A subtree is a node together with all of its descendants, and it is itself a binary tree.
Why Counting Nodes Is Trickier Than It Looks
Counting the nodes of a binary tree looks like the easiest question you could ask about one. How many nodes does this tree contain? Many learners expect the answer to come from a single pass through the structure, with a loop that visits each node and adds one to a running total. That expectation is the misconception this article examines.
The difficulty is that a binary tree does not hand you its nodes in a neat list. Each node can lead to two different branches. Once you move down one branch you must still remember that the other branch exists, and a flat loop has no natural place to keep that pending work. Counting nodes is hard to do without recursion for exactly this reason: pending nodes must be tracked somehow.
The good news is that once you think in terms of subtrees, the problem becomes almost trivial. The rest of this article builds that reasoning step by step, starting with the vocabulary you need: a subtree, the root, and the left and right branches.
Predicting the Size of a Six-Node Tree
Consider a binary tree whose root is the node 1. The root has a left child 2 and a right child 3. Node 2 has two children, 4 and 5. Node 3 has one child, 6. Nodes 4, 5, and 6 have no children of their own.
What do you think happens?
Before reading on, how many nodes does this tree contain in total? Try counting by a method of your own.
Reveal answer
6
The tree holds the nodes 1, 2, 3, 4, 5, and 6. Each of these is counted exactly once, which gives six. The rest of this article shows how a recursive method arrives at the same total by combining the counts of smaller subtrees.
Splitting a Tree into Root and Subtrees
A subtree is a node together with all of its descendants, meaning its children, its children's children, and so on. The collection of nodes you gather in this way forms a binary tree in its own right, and that tree is called a subtree of the original tree. Because every node has its own subtree, subtrees appear at every level of the structure, nested inside one another.
This gives a very useful way to describe any tree. A non-empty binary tree can be viewed as three pieces: a root node, a left subtree, and a right subtree. Either subtree, or both, may be empty. The diagram below shows this split for the six-node tree. The root is the node 1 at the top. The left branch hangs off to a subtree rooted at 2, and the right branch hangs off to a subtree rooted at 3.
Notice that the root itself is not part of either subtree. The left subtree contains 2, 4, and 5. The right subtree contains 3 and 6. Each subtree is a complete binary tree that happens to sit inside a larger one.
The Recursive Counting Rule
Now the counting rule can be stated. The count for an empty tree is zero. This is the base case, and it is what stops the recursion. For a tree that has a root, the count is the number of nodes in the left subtree, plus the number in the right subtree, plus one for the root itself. The routine is applied to each subtree, and the results are combined by addition.
- 1
count(left subtree)asks the same question about a smaller tree, which may itself be empty - 2
count(right subtree)does the same for the other branch - 3the plus one accounts for the root node, which belongs to neither subtree
- 4the three results are added to give the total for the current tree
Tracing the Returns Back Up the Tree
A recursive count does not finish in one visible step. Each call to the counting routine starts another call on a smaller subtree, and it cannot produce its own answer until the calls beneath it have returned. The diagram below shows one call for each non-empty subtree in the six-node tree. Empty subtrees are left out because each of them returns zero immediately. Read the diagram from the top: the call for the root begins first, and the results travel back up as the calls finish.
Combining Returned Counts at Each Node
Use the recursive counting rule to find the total number of nodes in the six-node tree, showing how each call combines the values returned by its subtrees.
- 1Base case on empty subtrees
The empty left and right subtrees of node 4, node 5, and node 6 each return 0 immediately.
- 2Leaves return 1
The call on node 4 gets 0 from the left and 0 from the right, then adds 1 for itself, returning 1. The call on node 5 does the same and returns 1.
- 3Node 2 combines its children
The call on node 2 receives 1 from node 4 and 1 from node 5, then adds 1 for itself. It returns 1 + 1 + 1 = 3.
- 4Node 3 combines its children
The call on node 3 receives 1 from its right child 6 and 0 from its empty left subtree, then adds 1 for itself. It returns 1 + 0 + 1 = 2.
- 5Root combines both subtrees
The call on the root receives 3 from the left and 2 from the right, then adds 1 for itself. It returns 3 + 2 + 1 = 6.
The root call returns 6, which matches the six nodes in the tree.
Notice how the return values combine. Each call contributes only its own single node plus whatever its children report back. No loop has to remember the pending branches. The call stack that the language already maintains does that bookkeeping automatically, which is the reason recursion fits trees so well.
Mistakes When Reasoning About Subtrees
Common mistake Treating the root as part of its own subtrees
What it looks likeSaying the left subtree of the six-node tree contains 1, 2, 4, and 5.
Why it failsThe subtrees are the children and their descendants. The root sits above both subtrees and is not inside either one.
Do this insteadThe left subtree of the six-node tree contains 2, 4, and 5. The root is counted separately with the plus one.
Common mistake Forgetting the base case for an empty tree
What it looks likeWriting a counting routine that tries to read the left child of a node that has no children.
Why it failsSubtrees can be empty. Without a stopping rule for the empty tree, the recursion never bottoms out.
Do this insteadReturn 0 whenever the tree is empty, before any attempt to look at children.
Common mistake Assuming a single loop can count without extra bookkeeping
Why it failsA flat loop has no built-in memory of the branches it has not yet visited, so it needs extra structures to track them.
Common mistake Adding the subtree counts without the root
What it looks likeReturning left plus right for the six-node tree and getting 5.
Why it failsEvery non-empty tree contributes one root node that neither subtree includes.
Do this insteadReturn left plus right plus one, giving 3 + 2 + 1 = 6.
Applying the Rule to a Smaller Tree
A new tree has root 10. Its left child is 20, which has no children. Its right child is 30, which has one left child, 40. No other nodes exist.
Using the recursive counting rule, work out the count returned by each call, starting from node 40 and working up to the root 10. What total does the root call return?
Hints
- Start with the calls on empty subtrees. Each returns 0.
- Node 40 has two empty subtrees, so it returns 0 + 0 + 1.
- Node 30 combines its left subtree rooted at 40 with an empty right subtree and adds 1 for itself.
- The root 10 adds the count of node 20, which is 1, to the count of node 30, then adds 1 for itself.
Key Takeaways
- A subtree is a node together with all of its descendants, and it is itself a binary tree.
- A non-empty binary tree can be viewed as a root, a left subtree, and a right subtree, where either subtree or both may be empty.
- The recursive counting rule is zero for an empty tree, and otherwise the left count plus the right count plus one for the root.
- Recursive calls return their counts upward, and the call stack handles the bookkeeping that a flat loop would otherwise need extra structures to manage.