Count Total Nodes in Binary Tree in DSA C++ - Execution Trace

Concept Flow - Count Total Nodes in Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Count left subtree nodes

↓

Count right subtree nodes

↓

Add 1 (current node) + left count + right count

↓

Return total count

The process starts at the root, recursively counts nodes in left and right subtrees, then adds 1 for the current node.

Execution Sample

DSA C++

int countNodes(Node* root) {
  if (root == nullptr) return 0;
  return 1 + countNodes(root->left) + countNodes(root->right);
}

This function counts all nodes in a binary tree by recursively summing nodes in left and right subtrees plus the current node.

Execution Table

Step	Operation	Node Visited	Left Count	Right Count	Total Count	Tree State
1	Visit root	1	-	-	-	1 / \ 2 3
2	Visit left child	2	-	-	-	1 / \ 2 3
3	Visit left child's left child	4	-	-	-	1 / \ 2 3 / 4
4	Left child of 4 is null	null	0	-	-	1 / \ 2 3 / 4
5	Right child of 4 is null	null	-	0	-	1 / \ 2 3 / 4
6	Count nodes at 4	4	0	0	1	1 / \ 2 3 / 4
7	Visit right child of 2	5	-	-	-	1 / \ 2 3 / \ 4 5
8	Left child of 5 is null	null	0	-	-	1 / \ 2 3 / \ 4 5
9	Right child of 5 is null	null	-	0	-	1 / \ 2 3 / \ 4 5
10	Count nodes at 5	5	0	0	1	1 / \ 2 3 / \ 4 5
11	Count nodes at 2	2	1	1	3	1 / \ 2 3 / \ 4 5
12	Visit right child	3	-	-	-	1 / \ 2 3 / \ 4 5
13	Left child of 3 is null	null	0	-	-	1 / \ 2 3 / \ 4 5
14	Right child of 3 is null	null	-	0	-	1 / \ 2 3 / \ 4 5
15	Count nodes at 3	3	0	0	1	1 / \ 2 3 / \ 4 5
16	Count nodes at root	1	3	1	5	1 / \ 2 3 / \ 4 5
17	Return total count	-	-	-	5	1 / \ 2 3 / \ 4 5

💡 All nodes visited; recursion ends when null nodes are reached returning 0.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
Current Node	1	4	4	5	2	3	1	-
Left Count	-	0	0	0	1	0	3	-
Right Count	-	-	0	0	1	0	1	-
Total Count	-	-	1	1	3	1	5	5

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 at null nodes (see Step 4 and Step 8) stops recursion and counts no nodes beyond leaf ends.

How does the function add counts from left and right subtrees?

At each node (e.g., Step 11), the function adds 1 (current node) plus counts returned from left and right recursive calls.

Why does the total count at root equal 5?

Because it sums all nodes counted in left subtree (3), right subtree (1), plus itself (1), as shown in Step 16.

Visual Quiz - 3 Questions

Look at the execution table, what is the total count after visiting node 2 (Step 11)?

A 2

B 3

C 1

D 5

💡 Hint

Check the 'Total Count' column at Step 11 in the execution table.

At which step does the function return 0 for a null node?

A Step 6

B Step 11

C Step 4

D Step 16

💡 Hint

Look for steps where 'Node Visited' is 'null' and 'Left Count' or 'Right Count' is 0.

If the right subtree of node 1 had one more node, how would the total count at root (Step 16) change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Total count sums all nodes; adding one node in right subtree adds 1 to total count at root.

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is null, return 0
- Else return 1 + count(left) + count(right)
- Counts all nodes including root
- Stops when leaf children are null

Full Transcript

This concept shows how to count all nodes in a binary tree using recursion. Starting at the root, the function visits each node, counts nodes in the left subtree, counts nodes in the right subtree, then adds 1 for the current node. When a null node is reached, it returns 0 to stop recursion. The execution table traces each step visiting nodes 1, 2, 4, 5, and 3, showing counts returned from subtrees and total counts computed. The variable tracker shows how counts accumulate. Key moments clarify why null nodes return 0, how counts add up, and why the final total is 5. The visual quiz tests understanding of counts at specific steps and effects of adding nodes. This method ensures every node is counted exactly once.